题解 P3644 【[APIO2015]八邻旁之桥】
这题用什么平衡树线段树...两个堆就可以搞定了
不就是常数大一点一样能过
首先分析一下题面，只能修一座或两座桥。如果某个人的家和办公室在一侧，那么不用过桥，可以预处理，同时，家和办公室不在一侧的，必定要过桥，可以先预处理桥的那个长度（1）。
下面分类讨论（忽视所有不用过桥的人）：
（1）K=1,那么每个人都要先走到桥，再过桥，再通过对岸走到办公室，那么在两岸走的距离实际上就是每个人的家到桥和办公室到桥的距离和，如果有tot个人，那么这个问题就抽象成：一条直线上有2*tot个点，要找一个点使得其到所有点距离和最小，这个点就是所有点位置的中位数。
静态中位数是比较容易求的，只要对数组进行一次排序，返回位于最中间的值就可以了，这道题点始终是偶数个，所以中间两个点选哪个都可以。
（2）K=2，这个时候其实是把所有人分成两个区域，划分标准应该是家与办公室的坐标和（这个有很多题解已经说到了，不再证明了），左侧的人走左边的桥，右侧的人走右边的桥。那么我们可以枚举中间的分界点，然后左右分别是一个K=1的子问题，关键在于怎么快速得出左右两边的最小距离和。
这其实是一个动态中位数问题，我们要求出排序后每个前缀和每个后缀的中位数，这可以参考P1168中位数，只需要用一个大根堆和一个小根堆，用大根堆维护较小的一半的数，用小根堆维护较大一半的数，每次来一对新的数时，先插入大根堆，此时两个堆不平衡，要把大根堆的堆顶（也就是最接近中间的那个数）移到小根堆上，然后再做检测，如果大根堆的堆顶比小根堆堆顶还大，那么交换两个堆顶。
进一步抽象，其实我们现在已经将某个前缀/后缀分成了左右两块，实际上这里的最小距离和就是：右侧点坐标和减去左侧点坐标和，我们可以理解为是每个左侧点与一个右侧点配对，它们的连线一定经过中间的中位数，所以它们的坐标差即是最小距离和。如此一来，我们只需在堆中插入元素时更新左右坐标和，就可以得到某个前缀/后缀的最小距离和。
整理一下思路：先按家与办公室坐标和排序，然后预处理每个前缀和每个后缀的距离和，最后枚举中间的断点，将断点两侧的距离和相加就是一种可能的答案，在所有可能答案中选取最小值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
struct P {
int a,b;
}p[MAXN];
int k,n,tot,cnt,x1,x2,pl[MAXN];
long long ans,haf[2][MAXN],s1,s2; //ans是预处理值,haf[0]是前缀距离,haf[1]是后缀距离,s1是左侧坐标和,s2是右侧坐标和
char c1,c2;
priority_queue <int,vector<int>,less<int> > q1;
priority_queue <int,vector<int>,greater<int> > q2;
bool cmp (P a,P b) {
return a.a+a.b<b.a+b.b; //按照家和办公室坐标和排序
}
int main () {
cin >> k >> n;
for (int i=1;i<=n;i++) {
cin >> c1 >> x1>> c2 >> x2;
if (c1==c2) {
ans+=abs(x2-x1);
} else {
ans++,p[++tot].a=x1;
p[tot].b=x2,pl[++cnt]=x1;
pl[++cnt]=x2;
}
}
if (k==1) {
sort(pl+1,pl+cnt+1);
int pos=pl[cnt/2];
for (int i=1;i<=cnt;i++) {
ans+=abs(pl[i]-pos);
}
cout << ans << endl;
} else {
sort(p+1,p+tot+1,cmp);
for (int i=1;i<=tot;i++) {
q1.push(p[i].a),q1.push(p[i].b);
s1+=p[i].a+p[i].b;
s2+=q1.top(),s1-=q1.top(),q2.push(q1.top());
q1.pop();
if (q1.top()>q2.top()) { //交换堆顶
int t=q2.top(),l=q1.top();
q2.pop(),q1.pop();
q2.push(l),q1.push(t);
s1+=t-l,s2-=t-l;
}
haf[0][i]=s2-s1; //左右坐标和的差即为最小距离和
}
while (!q1.empty()) {
q1.pop();
}
while (!q2.empty()) {
q2.pop();
}
s1=s2=0;
for (int i=tot;i>=1;i--) {
q1.push(p[i].a),q1.push(p[i].b);
s1+=p[i].a+p[i].b;
s2+=q1.top(),s1-=q1.top(),q2.push(q1.top());
q1.pop();
if (q1.top()>q2.top()) { //交换堆顶
int t=q2.top(),l=q1.top();
q2.pop(),q1.pop();
q2.push(l),q1.push(t);
s1+=t-l,s2-=t-l;
}
haf[1][i]=s2-s1; //左右坐标和的差即为最小距离和
}
long long mn=1e18;
for (int i=1;i<=tot+1;i++) {
mn=min(mn,haf[0][i-1]+haf[1][i]);
}
cout << mn+ans; //别忘加上预处理的值
}
return 0;
}