BZOJ（这题是BZOJ权限题，有权限号的就去看看吧）
Luogu（良心洛谷）
题目描述
一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域(A)和区域(B)。
每一块区域沿着河岸都建了恰好(1000000001)栋的建筑，每条岸边的建筑都从(0 编号到 1000000000)。相邻的每对建筑相隔(1)个单位距离，河的宽度也是(1)个单位长度。区域(A)中的(i)号建筑物恰好与区域(B)中的(i)号建筑物隔河相对。
城市中有(N)个居民。第(i)个居民的房子在区域(P_i)的(S_i)号建筑上，同时他的办公室坐落在(Q_i)区域的(T_i)号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便。为了使居民们可以开车去工作，政府决定建造不超过(K)座横跨河流的大桥。
由于技术上的原因，每一座桥必须刚好连接河的两岸，桥梁必须严格垂直于河流，并且桥与桥之间不能相交。
当政府建造最多(K)座桥之后，设(D_i)表示第(i)个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁，使得 (D1+D2+⋯+DN)最小。
输入格式：
输入的第一行包含两个正整数(K)和(N)，分别表示桥的上限数量和居民的数量。
接下来(N)行，每一行包含四个参数：(P_i,S_i,Q_i)和(T_i)，表示第(i)个居民的房子在区域(P_i)的(S_i)号建筑上，且他的办公室位于(Q_i)区域的(T_i)号建筑上。
输出格式：
输出仅为一行，包含一个整数，表示(D1+D2+⋯+DN)的最小值.
输入样例#1：
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
输出样例#1：
24
输入样例#2：
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
输出样例#2：
22
说明
所有数据都保证：(P_i) 和 (Q_i) 为字符 (“A”) 和 (“B”) 中的一个， (0≤S_i,T_i≤10000000000) ，同一栋建筑内可能有超过 (1) 间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 (1)）。
子任务 1 （8 分）(K=1quad1≤N≤1000)
子任务 2 （14 分）(K=1quad1≤N≤100000)
子任务 3 （9 分）(K=2quad1≤N≤100)
子任务 4 （32 分）(K=2quad1≤N≤1000)
子任务 5 （37 分）(K=2quad1≤N≤100000)
sol
这题看上去很不可做呀，但是很明显(K≤2)这个条件是非常重要的。
先考虑(K=1)怎么做。
首先，如果一个人的房子和办公室位于河的同一侧，那么这个人肯定是不受任何影响的，即他对答案的贡献永不变。我们先把这种人预处理了，然后剩下的全是必须要过河的。
那么现在有(cnt)个人要过河，第(i)个人要从(A_i)走到(B_i)，或者说，从(A_i)走到桥的位置(pos)，再从桥的位置(pos)走到(B_i)。说白了我们就是要求(sum abs(A_i-pos)+abs(B_i-pos))，可发现(A_i)与(B_i)其实无差别。
所以就把所有的(A_i)跟(B_i)放在一起排序，然后桥的位置就一定是排序后中位数的位置。暴力统计每个点到桥的距离，这样(K=1)就做完了。
现在来考虑(K=2)。
首先看这样一个结论：对每个人来说，他一定会走那座离((A_i+B_i)/2)更近的桥。这个结论其实不需要证明，手玩一下即可。
那么我们把所有人按照((A_i+B_i)/2)排序，那么一定是左边一部分人走左边的那座桥，右边的一部分人走右边的那座桥。
所以我们要对左右分别维护一个数据结构，支持快速插入、删除元素，并可以快速查询中位数、查询区间和。在这里splay和权值线段树都是不错的选择。
那么这题就做完啦。嗯哼。
code
本代码使用权值线段树。
本代码使用cin读入数据。
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 100005;
struct node{
int u,v;
bool operator < (const node &b) const
{return u+v<b.u+b.v;}
}x[N];
int n,k,a,b,o[N<<1],len,sz[2][N<<3],cnt;
ll useless,tot1,tot2,sum[2][N<<3],ans;
char op1,op2;
void work1()
{
for (int i=1;i<=n;i++)
{
cin>>op1>>a>>op2>>b;
if (op1==op2) useless+=abs(a-b);
else useless++,o[++len]=a,o[++len]=b;
}
sort(o+1,o+len+1);
for (int i=1;i<=(len>>1);i++)
tot1+=o[i];
for (int i=(len>>1)+1;i<=len;i++)
tot2+=o[i];
cout<<useless+tot2-tot1<<endl;
}
void Modify(int w,int x,int l,int r,int pos,int tp)
{
sz[w][x]+=tp;
sum[w][x]+=tp*o[pos];
if (l==r) return;
int mid=l+r>>1;
if (pos<=mid) Modify(w,x<<1,l,mid,pos,tp);
else Modify(w,x<<1|1,mid+1,r,pos,tp);
}
int Find(int w,int x,int l,int r,int k)
{
if (l==r) return l;
int mid=l+r>>1;
if (k<=sz[w][x<<1]) return Find(w,x<<1,l,mid,k);
else return Find(w,x<<1|1,mid+1,r,k-sz[w][x<<1]);
}
int Size(int w,int x,int l,int r,int ql,int qr)
{
if (l>=ql&&r<=qr) return sz[w][x];
int mid=l+r>>1,s=0;
if (ql<=mid) s+=Size(w,x<<1,l,mid,ql,qr);
if (qr>mid) s+=Size(w,x<<1|1,mid+1,r,ql,qr);
return s;
}
ll Sum(int w,int x,int l,int r,int ql,int qr)
{
if (l>=ql&&r<=qr) return sum[w][x];
int mid=l+r>>1;ll s=0;
if (ql<=mid) s+=Sum(w,x<<1,l,mid,ql,qr);
if (qr>mid) s+=Sum(w,x<<1|1,mid+1,r,ql,qr);
return s;
}
void work2()
{
for (int i=1;i<=n;i++)
{
cin>>op1>>a>>op2>>b;
if (op1==op2) useless+=abs(a-b);
else useless++,o[++len]=a,o[++len]=b,x[++cnt]=(node){a,b};
}
if (!cnt) {cout<<useless<<endl;exit(0);}
sort(x+1,x+cnt+1);
sort(o+1,o+len+1);
len=unique(o+1,o+len+1)-o-1;
for (int i=1;i<=cnt;i++)
{
x[i].u=lower_bound(o+1,o+len+1,x[i].u)-o;
x[i].v=lower_bound(o+1,o+len+1,x[i].v)-o;
}
for (int i=1;i<=cnt;i++)
Modify(1,1,1,len,x[i].u,1),Modify(1,1,1,len,x[i].v,1);
ans=1e18;
for (int i=1;i<=cnt;i++)
{
Modify(0,1,1,len,x[i].u,1);Modify(0,1,1,len,x[i].v,1);
Modify(1,1,1,len,x[i].u,-1);Modify(1,1,1,len,x[i].v,-1);
int m1=Find(0,1,1,len,i),m2=Find(1,1,1,len,cnt-i);
ll D1=(ll)Size(0,1,1,len,1,m1)*o[m1]-Sum(0,1,1,len,1,m1)+Sum(0,1,1,len,m1,len)-(ll)Size(0,1,1,len,m1,len)*o[m1];
ll D2=(ll)Size(1,1,1,len,1,m2)*o[m2]-Sum(1,1,1,len,1,m2)+Sum(1,1,1,len,m2,len)-(ll)Size(1,1,1,len,m2,len)*o[m2];
ans=min(ans,D1+D2);
}
cout<<useless+ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin>>k>>n;
if (k==1) work1();
else work2();
return 0;
}