【BZOJ4071】[Apio2015]巴邻旁之桥
Description
一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 A 和区域 B。
每一块区域沿着河岸都建了恰好 1000000001 栋的建筑，每条岸边的建筑都从 0 编号到 1000000000。相邻的每对建筑相隔 1 个单位距离，河的宽度也是 1 个单位长度。区域 A 中的 i 号建筑物恰好与区域 B 中的 i 号建筑物隔河相对。
城市中有 N 个居民。第 i 个居民的房子在区域 Pi 的 Si 号建筑上，同时他的办公室坐落在 Qi 区域的 Ti 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，*决定建造不超过 K 座横跨河流的大桥。
由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。当*建造最多 K 座桥之后，设 Di 表示第 i 个居民此时开车从家里到办公室的最短距离。请帮助*建造桥梁，使得 D1+D2+⋯+DN 最小。
Input
输入的第一行包含两个正整数 K 和 N，分别表示桥的上限数量和居民的数量。
接下来 N 行，每一行包含四个参数：Pi,Si,Qi 和 Ti，表示第 i 个居民的房子在区域 Pi 的 Si 号建筑上，且他的办公室位于 Qi 区域的 Ti 号建筑上。
Output
输出仅为一行，包含一个整数，表示 D1+D2+⋯+DN 的最小值。
Sample Input
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
Sample Output
24
HINT
子任务
所有数据都保证：Pi 和 Qi 为字符 “A” 和 “B” 中的一个， 0≤Si,Ti≤1000000000，同一栋建筑内可能有超过 1 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 1）。
子任务 1 （8 分）
K=1
1≤N≤1000
子任务 2 （14 分）
K=1
1≤N≤100000
子任务 3 （9 分）
K=2
1≤N≤100
子任务 4 （32 分）
K=2
1≤N≤1000
子任务 5 （37 分）
K=2
1≤N≤100000
题解：先把不需要过桥的长度处理出来，别忘了桥的长度为1
当只有一座桥时，设位置为k，答案为∑(|ai-k|+|bi-k|)，显然我们只要将ai,bi放在一起排序，取中位数就行了
当有两座桥时，我们设位置为k1,k2，那么对于第i个人，他选择kj(j=1,2)的长度为|ai-k1|+|bi-k1|，这个值有几种情况:
1. |ai-bi| 2. |2*kj-ai-bi|
发现他肯定会选择距离ai+bi较近的那座桥，也就是说，当我们确定了两座桥的位置后，存在一个临界值mid，使得ai+bi比mid小的都选择k1，ai+bi比mid大的都选择k2
所以我们将人按照ai+bi排序，枚举这个分界线，然后两边分别按照只有一座桥的情况处理，这就需要我们动态维护中位数+统计答案，用treap轻松搞定
注意：当可以建两座桥的时候，也要讨论只建一座桥的情况！
时间上线20s，我跑了17s，我的代码是由多丑~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn=200010;
ll N,n,m,tot,r1,r2;
ll ans,tans,sum;
char sa[5],sb[5];
ll v[maxn<<2],s[maxn<<2],cnt[maxn<<2],siz[maxn<<2];
ll key[maxn<<2],ch[maxn<<2][2];
struct node
{
ll A,B;
}p[maxn];
bool cmp(node a,node b)
{
return a.A+a.B<b.A+b.B;
}
void pushup(ll x)
{
s[x]=v[x]*cnt[x]+s[ch[x][0]]+s[ch[x][1]];
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}
void rotate(ll &x,ll d)
{
ll y=ch[x][d];
ch[x][d]=ch[y][d^1],ch[y][d^1]=x;
pushup(x),pushup(y);
x=y;
}
void insert(ll &x,ll y)
{
if(!x)
{
x=++tot;
s[x]=v[x]=y,key[x]=rand(),cnt[x]=siz[x]=1;
return ;
}
siz[x]++;
if(y==v[x])
{
cnt[x]++,s[x]+=y;
return ;
}
ll d=(y>v[x]);
insert(ch[x][d],y);
if(key[ch[x][d]]>key[x]) rotate(x,d);
pushup(x);
}
void query(ll x,ll y)
{
if(!x) return ;
if(siz[ch[x][0]]>=y)
{
sum+=v[x]*cnt[x]+s[ch[x][1]];
query(ch[x][0],y);
return ;
}
if(siz[ch[x][0]]+cnt[x]>=y)
{
sum+=s[ch[x][1]]-s[ch[x][0]];
sum+=(2*siz[ch[x][0]]+cnt[x]-2*y)*v[x];
return ;
}
sum-=s[ch[x][0]]+v[x]*cnt[x];
query(ch[x][1],y-siz[ch[x][0]]-cnt[x]);
}
void del(ll &x,ll y)
{
if(v[x]==y)
{
if(cnt[x]>1)
{
cnt[x]--,siz[x]--,s[x]-=y;
return ;
}
if(ch[x][0]*ch[x][1]==0)
{
x=ch[x][0]+ch[x][1];
return ;
}
ll d=(key[ch[x][1]]>key[ch[x][0]]);
rotate(x,d),siz[x]--,s[x]-=y;
del(ch[x][d^1],y);
return ;
}
siz[x]--,s[x]-=y;
del(ch[x][y>v[x]],y);
return ;
}
int main()
{
scanf("%d%d",&m,&N);
ll a,b,i;
for(i=1;i<=N;i++)
{
scanf("%s%lld%s%lld",sa,&a,sb,&b);
if(a>b) swap(a,b);
if(sa[0]==sb[0]) tans+=b-a;
else p[++n].A=a,p[n].B=b;
}
tans+=n;
sort(p+1,p+n+1,cmp);
if(m==1)
{
for(i=1;i<=n;i++) insert(r1,p[i].A),insert(r1,p[i].B);
query(r1,n);
printf("%lld",tans+sum);
return 0;
}
for(i=1;i<=n;i++) insert(r2,p[i].A),insert(r2,p[i].B);
sum=0; query(r2,n);
ans=tans+sum;
for(i=1;i<=n;i++)
{
del(r2,p[i].A),del(r2,p[i].B);
insert(r1,p[i].A),insert(r1,p[i].B);
sum=0;
query(r1,i),query(r2,n-i);
ans=min(ans,tans+sum);
}
printf("%lld",ans);
return 0;
}