标签：turn new alt clu www isp inline scan 权值线段树
题目描述：
bz
luogu
题解：
贪心+权值线段树。
$K=1$的时候，答案为$\sum |x-l| + |x-r|$，所以所有端点排序后取中位数即可。
$K=2$的时候，一定是左边的一些走左边的桥，右边的一些走右边的桥。
问题是按什么顺序排序。
答案是按线段中点排序。
原因是，对于河两岸的一对点和两座桥，选择的一定是离线段中点近的那个。
考虑如何快速计算答案，我们可以用权值线段树维护区间和与中位数。（当然也可以用平衡树）
代码：
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 100050;
const int M = 100*N;
template
inline void read(T&x)
{
T f = 1,c = 0;char ch=getchar();
while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch‘9‘){c=c*10+ch-‘0‘;ch=getchar();}
x = f*c;
}
int K,n;
ll ans;
char op1[2],op2[2];
struct Point
{
int l,r;
Point(){}
Point(int l,int r):l(l),r(r){}
bool operator const Point&a)const{return l+ra.r;}
}p[N];
int s[N1],tl;
const int inf = 2000000001;
struct segtree
{
int rt,tot,ls[M],rs[M],siz[M];
ll sum[M];
void insert(int l,int r,int&u,int qx)
{
if(!u)u=++tot;siz[u]++,sum[u]+=qx;
if(l==r)return ;
int mid = (l+r)>>1;
if(qxmid)insert(l,mid,ls[u],qx);
else insert(mid+1,r,rs[u],qx);
}
void erase(int l,int r,int u,int qx)
{
siz[u]--,sum[u]-=qx;if(l==r)return ;
int mid = (l+r)>>1;
if(qxmid)erase(l,mid,ls[u],qx);
else erase(mid+1,r,rs[u],qx);
}
int query(int l,int r,int u,int rk)
{
if(!u)return -1;
if(l==r)return l;
int mid = (l+r)>>1;
if(rkreturn query(l,mid,ls[u],rk);
else return query(mid+1,r,rs[u],rk-siz[ls[u]]);
}
ll query(int l,int r,int u,int ql,int qr)
{
if(!u||ql>qr)return 0;
if(l==ql&&r==qr)return sum[u];
int mid = (l+r)>>1;
if(qrreturn query(l,mid,ls[u],ql,qr);
else if(ql>mid)return query(mid+1,r,rs[u],ql,qr);
else return query(l,mid,ls[u],ql,mid)+query(mid+1,r,rs[u],mid+1,qr);
}
ll Query(int l,int r,int u,int ql,int qr)
{
if(!u||ql>qr)return 0;
if(l==ql&&r==qr)return siz[u];
int mid = (l+r)>>1;
if(qrreturn Query(l,mid,ls[u],ql,qr);
else if(ql>mid)return Query(mid+1,r,rs[u],ql,qr);
else return Query(l,mid,ls[u],ql,mid)+Query(mid+1,r,rs[u],mid+1,qr);
}
ll query(int siz)
{
int mid = query(0,inf,rt,siz);
ll ql = query(0,inf,rt,0,mid-1),qr = query(0,inf,rt,mid+1,inf),tmp = (Query(0,inf,rt,mid+1,inf)-Query(0,inf,rt,0,mid-1));
return qr-ql-tmp*mid;
}
}tr[2];
int main()
{
// freopen("tt.in","r",stdin);
read(K),read(n);
for(int x,y,i=1;i)
{
scanf("%s",op1),read(x),scanf("%s",op2),read(y);
if(x>y)swap(x,y);
if(op1[0]==op2[0])
{
ans+=y-x;
i--,n--;
}else p[i]=Point(x,y);
}
ans+=n;
if(!n)
{
printf("%lld\n",ans);
return 0;
}
if(K==1)
{
for(int i=1;i)
s[++tl]=p[i].l,s[++tl]=p[i].r;
sort(s+1,s+tl+1);
int mid = (s[tl/2]+s[tl/2+1])/2;
int i;
for(i=1;s[i]s[i];
for(;imid;
printf("%lld\n",ans);
return 0;
}
sort(p+1,p+1+n);
for(int i=1;i)
tr[1].insert(0,inf,tr[1].rt,p[i].l),tr[1].insert(0,inf,tr[1].rt,p[i].r);
ll mx = 0x3f3f3f3f3f3f3f3fll;
for(int i=1;i)
{
tr[0].insert(0,inf,tr[0].rt,p[i].l),tr[0].insert(0,inf,tr[0].rt,p[i].r);
tr[1].erase (0,inf,tr[1].rt,p[i].l),tr[1].erase (0,inf,tr[1].rt,p[i].r);
mx=min(mx,tr[0].query(i)+tr[1].query(n-i));
}
printf("%lld\n",ans+mx);
return 0;
}
View Code
APIO2015 八邻旁之桥/巴邻旁之桥
标签：turn new alt clu www isp inline scan 权值线段树
原文地址：https://www.cnblogs.com/LiGuanlin1124/p/11094530.html