http://uoj.ac/problem/112
先扣掉在同一侧的情况。
当\(k=1\)时，桥建在所有位置的中位数。
当\(k=2\)时，对于每个居民\((S_i,T_i)\)，这个居民只会走离\(\frac{S_i+T_i}2\)最近的桥，那么对所有\(\frac{S_i+T_i}2\)排序，最优方案一定满足排序后的居民从中间分开，左边的居民走左边的桥，右边的居民走右边的桥。
从左往右扫，不断加入“左边的居民”，“左边的桥”建在当前“左边的居民”的所有\(S_i\)和\(T_i\)的中位数上，动态维护这个中位数就可以了。右边同理，最后合并答案即可。
对于动态维护中位数，考虑到每次加两个数，中位数只会在相邻的位置间左右横跳，所以维护前驱和后继就可以了。这里可以用树状数组/权值线段树维护前驱后继（前缀最大值，后缀最小值）。
时间复杂度\(O(n\log n)\)。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100003;
struct node {
int x, y;
bool operator < (const node &A) const {
return x + y < A.x + A.y;
}
} Q[N];
ll ans = 0;
int H[N << 1], cnt = 0, n, k, Si, Ti, tot = 0;
char pi, qi;
namespace hahaha {
void solve() {
cnt = 0;
for (int i = 1; i <= tot; ++i)
H[++cnt] = Q[i].x, H[++cnt] = Q[i].y;
stable_sort(H + 1, H + cnt + 1);
ll sum, ret = 0;
for (int i = cnt >> 1; i >= 1; --i) ret += H[i];
sum = ret;
for (int i = (cnt >> 1) + 1; i <= cnt; ++i) sum += H[i];
ans += sum - (ret << 1);
printf("%lld\n", ans);
}
}
template <typename T> void check_max(T &a, T b) {if (b > a) a = b;}
template <typename T> void check_min(T &a, T b) {if (b < a) a = b;}
namespace miaomiaomiao {
ll f1[N], f2[N];
int bitsl[N << 1], bitsr[N << 1], id[N << 1];
bool cmp(int x, int y) {return (x > tot ? Q[x - tot].y : Q[x].x) < (y > tot ? Q[y - tot].y : Q[y].x);}
void insl(int x) {
for (int t = x; t <= cnt; t += t & -t)
check_max(bitsl[t], x);
}
void insr(int x) {
for (int t = x; t; t -= t & -t)
check_min(bitsr[t], x);
}
int findl(int x) {
int ret = 0;
for (int t = x - 1; t; t -= t & -t)
check_max(ret, bitsl[t]);
return ret;
}
int findr(int x) {
int ret = cnt + 1;
for (int t = x + 1; t <= cnt; t += t & -t)
check_min(ret, bitsr[t]);
return ret;
}
void work(ll *f) {
int mid = 0; ll ret = 0, sum = 0;
for (int i = 1; i <= cnt; ++i) bitsl[i] = 0, bitsr[i] = cnt + 1;
for (int i = 1; i <= tot; ++i) {
int x = Q[i].x, y = Q[i].y;
insl(x); insl(y);
insr(x); insr(y);
sum += H[x]; sum += H[y];
if (x < mid && y > mid || y < mid && x > mid)
ret += H[min(x, y)];
else if (x < mid) {
ret -= H[mid];
ret += H[x]; ret += H[y];
mid = findl(mid);
} else {
mid = findr(mid);
ret += H[mid];
}
f[i] = sum - (ret << 1);
}
}
void solve() {
for (int i = 1; i <= (tot << 1); ++i) id[i] = i;
stable_sort(Q + 1, Q + tot + 1);
stable_sort(id + 1, id + (tot << 1) + 1, cmp);
cnt = 0;
for (int i = 1; i <= (tot << 1); ++i) {
++cnt;
if (id[i] > tot) H[cnt] = Q[id[i] - tot].y, Q[id[i] - tot].y = cnt;
else H[cnt] = Q[id[i]].x, Q[id[i]].x = cnt;
}
work(f1);
reverse(Q + 1, Q + tot + 1);
work(f2);
ll ra = f2[tot];
for (int i = 1; i <= tot; ++i)
check_min(ra, f1[i] + f2[tot - i]);
printf("%lld\n", ans + ra);
}
}
int main() {
scanf("%d%d", &k, &n);
for (int i = 1; i <= n; ++i) {
for (pi = getchar(); pi != 'A' && pi != 'B'; pi = getchar());
scanf("%d", &Si);
for (qi = getchar(); qi != 'A' && qi != 'B'; qi = getchar());
scanf("%d", &Ti);
if (qi == pi) ans += abs(Ti - Si);
else {
Q[++tot] = (node) {Si, Ti};
++ans;
}
}
if (k == 1) hahaha::solve();
else miaomiaomiao::solve();
return 0;
}