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 最小。k<=2 n<=10^5
对于k=1的情况，代价为桥到所有Ai,Bi不同侧的Ai,Bi的距离，显然选择Ai,Bi的中位数建桥。对于k=2的情况，对于Ai,Bi，设桥的位置为p，那么代价为:
1.|Ai-Bi| 【p在二者中间】 2.|Ai+Bi-2*p|【p在二者同侧】
发现第二种等价到p的距离的二倍，那么对于第二种情况，每个Ai,Bi应当选择离二者中点近的桥，发现这个结论对于一情况也成立，尽可能的选择了在A,B之间的桥。
那么对于所有的Ai,Bi，我们对于它的中点排序，那么这个序列某个前缀是选择一个桥的，其余的选择另一个桥。转化为两个k=1的问题。枚举前缀，用平衡树SBT维护两段的代价即可（寻找中位数，加上比中位数大的，减去比其小的）。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef long long ll;
ll ans;
int n,m;
inline int Abs(int x){return x>0 ? x : -x;}
struct node
{
int l,r;
}a[N];
bool cmp(node x,node y){return x.l+x.r<y.l+y.r;}
queue<int>de;
int tot,rot1,rot2,siz1,siz2;
struct SBT
{
int ls,rs,siz,w;
ll sum;
}t[N<<1];
inline void newSBT(int &x)
{
if(de.size()) x=de.front(),de.pop();
else x=++tot;
}
inline void zig(int &x)
{
int l=t[x].ls;
t[x].ls=t[l].rs; t[l].rs=x;
t[l].siz=t[x].siz; t[l].sum=t[x].sum;
t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum+t[x].w;
x=l;
}
inline void zag(int &x)
{
int r=t[x].rs;
t[x].rs=t[r].ls; t[r].ls=x;
t[r].siz=t[x].siz; t[r].sum=t[x].sum;
t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum+t[x].w;
x=r;
}
void maintain(int &x,bool fl)
{
if(!fl)
{
if(t[t[t[x].ls].ls].siz>t[t[x].rs].siz) zig(x);
else if(t[t[t[x].ls].rs].siz>t[t[x].rs].siz) zag(t[x].ls),zig(x);
else return ;
}
else
{
if(t[t[t[x].rs].rs].siz>t[t[x].ls].siz) zag(x);
else if(t[t[t[x].rs].ls].siz>t[t[x].ls].siz) zig(t[x].rs),zag(x);
else return ;
}
maintain(t[x].ls,0); maintain(t[x].rs,1);
maintain(x,0); maintain(x,1);
}
void insert(int &k,int x)
{
if(!k)
{
newSBT(k),t[k].w=t[k].sum=x,t[k].siz=1;
return ;
}
t[k].siz++; t[k].sum+=x;
if(x<t[k].w) insert(t[k].ls,x);
else insert(t[k].rs,x);
maintain(k,x>=t[k].w);
}
void del(int &k,int x)
{
t[k].siz--; t[k].sum-=x;
if(x<t[k].w) del(t[k].ls,x);
else if(x>t[k].w) del(t[k].rs,x);
else
{
if(!t[k].ls||!t[k].rs)
{
int p=t[k].ls|t[k].rs;//
t[k].ls=t[k].rs=0;
de.push(k); k=p;
}
else
{
int p=t[k].ls; while(t[p].rs) p=t[p].rs;
t[k].w=t[p].w; int i=t[k].ls,las=k;
while(i!=p) t[i].siz--,t[i].sum-=t[p].w,las=i,i=t[i].rs;
if(p==t[las].ls) t[las].ls=t[p].ls;
else t[las].rs=t[p].ls;
t[p].ls=t[p].rs=0; de.push(p);
}
}
}
inline ll query(int x,int y)
{
ll re=0;
while(x)
{
int tmp=t[t[x].ls].siz;
if(y<=tmp)
{
re+=t[t[x].rs].sum+t[x].w;
x=t[x].ls;
}
else
{
y-=(tmp+1);
if(!y) return re-t[x].w-t[t[x].ls].sum+t[t[x].rs].sum;
re-=t[t[x].ls].sum+t[x].w; x=t[x].rs;
}
}
return 0;
}
int main()
{
scanf("%d%d",&m,&n);
int i=1; char s1[8],s2[8];
while(i<=n)
{
scanf("%s%d%s%d",s1,&a[i].l,s2,&a[i].r);
if(s1[0]==s2[0]) ans+=Abs(a[i].l-a[i].r),n--;
else
{
if(a[i].l>a[i].r) swap(a[i].l,a[i].r);
++i;
}
}
sort(a+1,a+n+1,cmp); ll tmp=0x3f3f3f3f3f3f3f3fll;
for(int i=1;i<=n;++i) insert(rot2,a[i].l),insert(rot2,a[i].r);
siz2=(n<<1);
tmp=min(tmp,query(rot2,siz2>>1));
if(m==1) ans+=tmp;
else
{
for(int i=1;i<n;++i)
{
del(rot2,a[i].l); del(rot2,a[i].r); siz2-=2;
insert(rot1,a[i].l); insert(rot1,a[i].r); siz1+=2;
tmp=min(tmp,query(rot1,siz1>>1)+query(rot2,siz2>>1));
}
ans+=tmp;
}
printf("%lld",ans+n);
return 0;
}