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
Sample Output
24
HINT
\(n\leqslant 10^5,k\in \{1,2\}\)。
Solution
在同侧的先预处理掉，过桥的\(1\)单位距离也预处理掉。
然后对于\(k=1\)的情况，桥显然要建在中位数上，\(splay\)维护下。
然后对于\(k=2\)的情况，显然有个断点，断点前的线段走第一座桥，断点后的线段走第二座桥，所以枚举断点，\(splay\)维护即可。
注意如果没有在河两侧的特判掉。
#include<bits/stdc++.h>
using namespace std;#define int long long void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}void print(int x) {
if(x<0) x=-x,putchar('-');
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);puts("");}const int maxn = 2e5+1;int k,n,m,ans;
struct node {
int l,r;
bool operator < (const node &rhs) const {return (l+r)<(rhs.l+rhs.r);}
}a[maxn],b[maxn];struct Splay_Tree {
int fa[maxn],son[maxn][2],sum[maxn],sz[maxn],val[maxn],rt,tot,cnt[maxn];
void update(int x) {
sum[x]=sum[son[x][0]]+sum[son[x][1]]+val[x]*cnt[x];
sz[x]=sz[son[x][0]]+sz[son[x][1]]+cnt[x];
}
int which(int x) {return son[fa[x]][1]==x;}
void rotate(int x) {
int f=fa[x],ff=fa[f],w=which(x);
if(ff) son[ff][son[ff][1]==f]=x;
fa[f]=x,fa[x]=ff,fa[son[x][w^1]]=f,son[f][w]=son[x][w^1],son[x][w^1]=f;
update(f),update(x);
}
void splay(int x) {
while(fa[x]) {
int y=fa[x],z=fa[y];
if(z) rotate(((son[y][1]==x)^(son[z][1]==y))?x:y);
rotate(x);
}update(x);rt=x;
}
int find(int x) {
int now=rt;
while(val[now]!=x) {
if(x<val[now]) {if(son[now][0]) now=son[now][0];else break;}
if(x>val[now]) {if(son[now][1]) now=son[now][1];else break;}
}
return now;
}
int newnode(int x) {val[++tot]=x,sz[tot]=cnt[tot]=1,sum[tot]=x;return tot;}
void insert(int x) {
if(!rt) return rt=newnode(x),void();
int now=find(x);
if(val[now]==x) return cnt[now]++,sz[now]++,splay(now),void();
son[now][val[now]<x]=newnode(x);fa[tot]=now;splay(now);
}
int kth(int kk) {
int now=rt;
while(1) {
if(kk<=sz[son[now][0]]) now=son[now][0];
else if(kk<=sz[son[now][0]]+cnt[now]) return now;
else kk-=sz[son[now][0]]+cnt[now],now=son[now][1];
}
}
int solve() {
int anss=0,now=kth(sz[rt]/2);splay(now);
anss=sz[son[rt][0]]*val[now]-sum[son[rt][0]]+sum[son[rt][1]]-sz[son[rt][1]]*val[now];
return anss;
}
}s,s2;int res[maxn];void solve() {
for(int i=1;i<=m;i++) {
s.insert(b[i].l),s.insert(b[i].r);
res[i]=s.solve();
}
if(k==1) return write(res[m]+ans);
int mn=1e18;
for(int i=m;i>=1;i--) {
s2.insert(b[i].l),s2.insert(b[i].r);
mn=min(mn,s2.solve()+res[i-1]);
}
write(mn+ans);
}signed main() {
read(k),read(n);
for(int i=1;i<=n;i++) {
char s1[3],s3[3];
scanf("%s",s1+1),read(a[i].l),scanf("%s",s3+1),read(a[i].r);
if(s1[1]==s3[1]) ans+=abs(a[i].l-a[i].r);
else ans++,b[++m]=a[i];
}
if(!m) return write(ans),0;
sort(b+1,b+m+1);
solve();
return 0;
}
