这题拿到后就瞬秒
\(k = 1\)的情况，跟一模一样。
所以我最后也只拿了31分……
正解要推出这么个性质，就是如果只有一座桥，那么所有城市和办公室的中位数就是这座桥的位置（然而我的
\(k = 1\)做法显然没有用到这一点……）。
怎么证明呢？
先用式子表示一下：就是我们要找到一个
\(x\)，满足
\(\sum_{i = 1} ^ {m} |L_i - x| + |R_i - x|\)最小，即
\(\sum _ {i = 1} ^ {2m} |a_i - x|\)最小。
假设
\(x\)现在是中位数，那么如果我们把
\(x\)变小或变大了一位（这里的“一位”指的是和某一个数的大小关系发生了改变），带来的代价就是
\(m * \Delta x - (m - 1) * \Delta x = \Delta x\)，这个值显然大于0，所以移动必定会带来正的代价。那么中位数就是最优的。
那么
\(k = 2\)的情况怎么办呢？
观察发现，每一个人的距离和
\(|L_i - R_i|\)以及距离桥的距离有关。因此我们取
\(L_i, R_i\)的中点，看中点离哪边的桥近就走哪边。
所以我们先把所有人按各自的中点排序（即
\(L_i + R_i\)），然后枚举两座桥的分界点，即分界点左侧的人都上一座桥，右侧的人上另一座桥。然后两边就变成了
\(k = 1\)的情况，分别求中位数即可。
因为要支持动态删点和加点，所以开两棵权值线段树，支持查找第
\(k\)大和区间求和操作。
找完中位数后计算答案的方法和上面说的那道题一样，用前缀和整体相减即可。
然后我因为按离散化后的值的中位数排序gg了好半天。
#include #include #include #include #include #include #include #include #include #include using namespace std;#define enter puts("") #define space putchar(' ')#define Mem(a, x) memset(a, x, sizeof(a))#define In inlinetypedef long long ll;typedef double db;const ll INF = 1e18;const db eps = 1e-8;const int maxn = 1e5 + 5;inline ll read(){ ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans;}inline void write(ll x){ if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0');}int K, n;char s1[2], s2[2];int a[maxn], b[maxn], t[maxn << 1], cnt[2];ll suma[maxn], sumb[maxn];In void work0(){ ll ans = INF, SUM = 0; for(int i = 1; i <= n; ++i) { scanf("%s", s1); int val1 = read(); scanf("%s", s2); int val2 = read(); if(s1[0] == s2[0]) SUM += abs(val1 - val2); else { a[++cnt[0]] = val1, b[cnt[0]] = val2; if(s1[0] == 'B') swap(a[cnt[0]], b[cnt[0]]); } } for(int i = 1; i <= cnt[0]; ++i) t[i] = a[i]; for(int i = 1; i <= cnt[0]; ++i) t[i + cnt[0]] = b[i]; sort(t + 1, t + (cnt[0] << 1) + 1); cnt[1] = unique(t + 1, t + (cnt[0] << 1) + 1) - t - 1; for(int i = 1; i <= cnt[0]; ++i) a[i] = lower_bound(t + 1, t + cnt[1] + 1, a[i]) - t; for(int i = 1; i <= cnt[0]; ++i) b[i] = lower_bound(t + 1, t + cnt[1] + 1, b[i]) - t; sort(a + 1, a + cnt[0] + 1), sort(b + 1, b + cnt[0] + 1); for(int i = 1; i <= cnt[0]; ++i) suma[i] = suma[i - 1] + t[a[i]]; for(int i = 1; i <= cnt[0]; ++i) sumb[i] = sumb[i - 1] + t[b[i]]; suma[cnt[0] + 1] = suma[cnt[0]]; sumb[cnt[0] + 1] = sumb[cnt[0]]; for(int i = 1, pos; i <= cnt[1]; ++i) { ll sum = 0; pos = lower_bound(a + 1, a + cnt[0] + 1, i) - a; if(pos > 0) sum = 1LL * t[i] * (pos - 1) - suma[pos - 1] + suma[cnt[0]] - suma[pos - 1] - 1LL * t[i] * (cnt[0] - pos + 1); pos = lower_bound(b + 1, b + cnt[0] + 1, i) - b; if(pos > 0) sum += 1LL * t[i] * (pos - 1) - sumb[pos - 1] + sumb[cnt[0]] - sumb[pos - 1] - 1LL * t[i] * (cnt[0] - pos + 1); ans = min(ans, sum); } if(ans == INF) ans = 0; write(ans + SUM + cnt[0]), enter;}struct Node{ int L, R; In bool operator < (const Node& oth)const { return L + R < oth.L + oth.R; }}q[maxn];int qcnt = 0, tot = 0;struct Tree{ int l[maxn << 3], r[maxn << 3], siz[maxn << 3]; ll sum[maxn << 3]; In void build(int L, int R, int now) { l[now] = L, r[now] = R; sum[now] = siz[now] = 0; if(L == R) return; int mid = (L + R) >> 1; build(L, mid, now << 1); build(mid + 1, R, now << 1 | 1); } In void pushup(int now) { sum[now] = sum[now << 1] + sum[now << 1 | 1]; siz[now] = siz[now << 1] + siz[now << 1 | 1]; } In void update(int id, int now, int flg) { if(l[now] == r[now]) { sum[now] += 1LL * t[id] * flg; siz[now] += flg; return; } int mid = (l[now] + r[now]) >> 1; if(id <= mid) update(id, now << 1, flg); else update(id, now << 1 | 1, flg); pushup(now); } In ll kth(int k, int now) { if(l[now] == r[now]) return t[l[now]] * k; if(siz[now << 1] >= k) return kth(k, now << 1); else return siz[now << 1] + kth(k - siz[now << 1], now << 1 | 1); } In ll query_low(int k, int now, db d) { if(l[now] == r[now]) return d * k - 1LL * t[l[now]] * k; if(siz[now << 1] > k) return query_low(k, now << 1, d); else if(siz[now << 1] == k) return d * siz[now << 1] - sum[now << 1]; else return d * siz[now << 1] - sum[now << 1] + query_low(k - siz[now << 1], now << 1 | 1, d); } In ll query_upp(int k, int now, db d) { if(l[now] == r[now]) return 1LL * t[l[now]] * k - d * k; if(siz[now << 1 | 1] > k) return query_upp(k, now << 1 | 1, d); else if(siz[now << 1 | 1] == k) return sum[now << 1 | 1] - d * siz[now << 1 | 1]; else return sum[now << 1 | 1] - d * siz[now << 1 | 1] + query_upp(k - siz[now << 1 | 1], now << 1, d); } In ll Query(int len) { if(!len) return 0; ll mid = kth(len >> 1, 1); return query_low(len >> 1, 1, mid) + query_upp(len >> 1, 1, mid); }}t1, t2;In void work1(){ ll ans = INF, SUM = 0; for(int i = 1; i <= n; ++i) { scanf("%s", s1); int val1 = read(); scanf("%s", s2); int val2 = read(); if(s1[0] == s2[0]) SUM += abs(val1 - val2); else q[++qcnt] = (Node){val1, val2}, t[++tot] = val1, t[++tot] = val2; } if(!qcnt) {write(SUM), enter; return;} sort(t + 1, t + tot + 1); tot = unique(t + 1, t + tot + 1) - t - 1; t1.build(1, tot, 1), t2.build(1, tot, 1); sort(q + 1, q + qcnt + 1); for(int i = 1; i <= qcnt; ++i) { q[i].L = lower_bound(t + 1, t + tot + 1, q[i].L) - t; q[i].R = lower_bound(t + 1, t + tot + 1, q[i].R) - t; t2.update(q[i].L, 1, 1), t2.update(q[i].R, 1, 1); } for(int i = 1; i <= qcnt + 1; ++i) { ll sum = t1.Query((i - 1) << 1) + t2.Query((qcnt - i + 1) << 1); ans = min(ans, sum); if(i > qcnt) break; t1.update(q[i].L, 1, 1), t1.update(q[i].R, 1, 1); t2.update(q[i].L, 1, -1), t2.update(q[i].R, 1, -1); } write(ans + SUM + qcnt), enter;}int main(){ K = read(), n = read(); if(K == 1) {work0(); return 0;} if(K == 2) {work1(); return 0;} return 0;}