BZOJ 4071 [Apio2015] 巴鄰旁之橋：中位數貪心與 Splay 維護動態中位數

題目大意

給定家與公司的位置，需選擇橋樑最小化總通勤距離。核心轉化：將不在同側的情況按區間中點排序，枚舉分割點，左側走左橋、右側走右橋，動態維護中位數計算最小距離和。

解法概覽

1. 預處理：同側家/公司直接累加曼哈頓距離
2. K=1 情況：經典中位數貪心，排序取中位數
3. K>1 情況：按區間中點 (x+y)/2 排序，枚舉分割點
4. 動態中位數維護：Splay 樹 / 權值線段樹支持插入、刪除、查詢中位數及距離和

關鍵數據結構：Splay 树實現

struct Node {
    int val, cnt, size;
    long long sum;
    int ch[2], fa;
} tr[N];

// 核心操作：旋轉、伸展、插入、刪除、查第 k 大、查前驅後繼
void rotate(int x) { ... }
void splay(int x, int goal) { ... }
void insert(int v) { ... }
void erase(int v) { ... }
int kth(int k) { ... }

// 查詢當前集合到中位數的距離和
long long query() {
    int mid = kth((size+1)/2);
    splay(mid, 0);
    // 利用左/右子樹 size 和 sum 計算 Σ|val - median|
}

複雜度分析

• 排序：O(M log M)
• 枚舉分割點：O(M)
• 每次 Splay 操作：O(log M) 攤還
• 總體：O(M log M)

代碼關鍵片段

// 主循環：枚舉分割點，動態維護左右兩邊的中位數
for (int i = 1; i <= m; ) {
    int j = i;
    // 同中點、同步長分組
    while (j <= m && same_group) j++;
    // 將該組加入左側 Splay
    for (int k = i; k < j; k++) left.insert(pos[k]);
    // 計算當前分割代價
    ans = min(ans, left.query() + right.query());
    // 將該組從右側移除（初始全在右側）
    for (int k = i; k < j; k++) right.erase(pos[k]);
    i = j;
}

避坑指南

• INF = 0x3f3f3f3f 別少寫一個 f
• Splay 伸展目標 goal=0 表示伸展到根
• 長長整型防溢出：距離和用 long long
• 離線處理：先排序再枚舉，避免在線動態插入的複雜度

總結

本題融合了幾何轉化（中點排序）、貪心枚舉分割、動態中位數維護（Splay）三大技術點。掌握 Splay 樹維護順序統計量（中位數、距離和）是解決此類動態平衡問題的利器。