一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 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 和 N，分别表示桥的上限数量和居民的数量。
接下来 N 行，每一行包含四个参数：Pi,Si,Qi 和 Ti，表示第 i 个居民的房子在区域 Pi 的 Si 号建筑上，且他的办公室位于 Qi 区域的 Ti 号建筑上。
输出
输出仅为一行，包含一个整数，表示 D1+D2+?+DN 的最小值。
样例输入
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
样例输出
24
题解
Treap
先把不需要过桥的距离、以及走在桥上的距离（河的宽度也是 1 个单位长度），把需要过桥的存到一个结构体中。
当k=1时，显然就是要最小化$\sum\limits_{i=1}^n(|s_i-p|+|t_i-p|)$，显然将s和t放到同一个数组里排序，取出中位数即为p。
当k=2时，考虑过桥的两种情况：s和t在桥的同侧、s和t在桥的两侧。
当两座桥都使得s和t在桥的同侧时，距离都为$|s_i+t_i-2p|$，这个值越小越好。
当某座桥使得s和桥在桥的两侧时，显然要走这座桥，距离为$|s_i-t_i|$，且这座桥的$|s_i+t_i-2p|$要小于使得s和t在桥的同侧时的$|s_i+t_i-2p|$。
综上所述，路线是和$s_i+t_i$相关的。我们可以枚举一个临界点，$s_i+t_i$小于这个临界点的都走第一座桥，$s_i+t_i$大于这个临界点的都走第二座桥。
那么相当于左右两个和k=1相同的问题。这里需要使用Treap维护区间中位数和区间绝对值和。
注意k=2时也要讨论只建一座桥的情况。
时间复杂度为$O(n\log n)$。
另外我代码写丑了，Treap的话不需要写结构体就可以开多个树。这里懒得改了。
#include <cstdio> #include <cstdlib> #include <algorithm> #define N 200010 using namespace std; typedef long long ll; struct data { ll px , py , ps; }a[N]; struct treap { int l[N] , r[N] , cnt[N] , si[N] , rnd[N] , root , tot; ll w[N] , sum[N]; void pushup(int k) { si[k] = si[l[k]] + si[r[k]] + cnt[k] , sum[k] = sum[l[k]] + sum[r[k]] + cnt[k] * w[k]; } void zig(int &k) { int t = l[k]; l[k] = r[t] , r[t] = k , pushup(k) , pushup(t) , k = t; } void zag(int &k) { int t = r[k]; r[k] = l[t] , l[t] = k , pushup(k) , pushup(t) , k = t; } void insert(int &k , ll x) { if(!k) { k = ++tot , si[k] = cnt[k] = 1 , sum[k] = w[k] = x , rnd[k] = rand(); return; } si[k] ++ , sum[k] += x; if(x == w[k]) cnt[k] ++ ; else if(x < w[k]) { insert(l[k] , x); if(rnd[l[k]] < rnd[k]) zig(k); } else { insert(r[k] , x); if(rnd[r[k]] < rnd[k]) zag(k); } } void erase(int &k , ll x) { si[k] -- , sum[k] -= x; if(x == w[k]) { if(cnt[k] > 1) cnt[k] -- ; else if(!l[k] || !r[k]) k = l[k] + r[k]; else if(rnd[l[k]] < rnd[r[k]]) zig(k) , erase(k , x); else zag(k) , erase(k , x); } else if(x < w[k]) erase(l[k] , x); else erase(r[k] , x); } ll find(int k , int x) { if(x <= si[l[k]]) return find(l[k] , x); else if(x > si[l[k]] + cnt[k]) return find(r[k] , x - si[l[k]] - cnt[k]); else return w[k]; } ll query(int k , ll x) { if(!k) return 0; else if(x < w[k]) return sum[r[k]] - x * si[r[k]] + cnt[k] * (w[k] - x) + query(l[k] , x); else if(x > w[k]) return x * si[l[k]] - sum[l[k]] + cnt[k] * (x - w[k]) + query(r[k] , x); else return x * si[l[k]] - sum[l[k]] + sum[r[k]] - x * si[r[k]]; } }A , B; char s1[5] , s2[5]; ll v[N]; bool cmp(data a , data b) { return a.ps < b.ps; } int main() { int k , n , i , num = 0; ll x , y , ans = 0 , sum = 0 , minn = 0x7fffffffffffffffll; scanf("%d%d" , &k , &n); for(i = 1 ; i <= n ; i ++ ) { scanf("%s%lld%s%lld" , s1 , &x , s2 , &y); if(s1[0] == s2[0]) ans += abs(x - y); else a[++num].px = x , a[num].py = y , a[num].ps = a[num].px + a[num].py , ans ++ ; } for(i = 1 ; i <= num ; i ++ ) v[i] = a[i].px , v[i + num] = a[i].py; sort(v + 1 , v + 2 * num + 1); for(i = 1 ; i <= 2 * num ; i ++ ) sum += abs(v[i] - v[num]); if(k == 2) { sort(a + 1 , a + num + 1 , cmp); for(i = 1 ; i <= num ; i ++ ) B.insert(B.root , a[i].px) , B.insert(B.root , a[i].py); for(i = 1 ; i < num ; i ++ ) { A.insert(A.root , a[i].px) , A.insert(A.root , a[i].py) , B.erase(B.root , a[i].px) , B.erase(B.root , a[i].py); minn = min(minn , A.query(A.root , A.find(A.root , A.si[A.root] / 2)) + B.query(B.root , B.find(B.root , B.si[B.root] / 2))); } } printf("%lld\n" , ans + min(sum , minn)); return 0; }
【bzoj4071】[Apio2015]巴邻旁之桥 Treap