BZOJ 4071 [APIO2015] 巴鄰旁之橋：中位數與動態維護區間最優橋址

問題背景

河流將城市分為 A、B 兩岸，各有 10⁹+1 棟建築。N 個居民家和辦公室分布在兩岸。政府最多建 K 座垂直橋樑（K=1 或 2），橋不可相交。居民選擇最近的橋通行，求最小化總通勤距離和。

核心洞察

• 同岸居民直接累加曼哈頓距離。
• 跨岸居民：家 (x) 和辦公室 (y) 中點為 (x+y)/2。居民會選擇距離其中點最近的橋。
• K=1：最優橋址為所有中點的中位數。
• K=2：按中點排序，枚舉分割點，左右兩段各按 K=1 處理。需動態維護區間中位數及距離和，用平衡樹（如 Treap）實現。

算法流程

1. 預處理同岸居民距離累加到答案。
2. 跨岸居民計算中點 mid = x+y（不除 2 不影響相對大小），按 mid 排序。
3. 正向掃描，維護左側居民的 x,y 集合，平衡樹查詢中位數及距離和，存入 f1[i]。
4. 反向掃描同理得 f2[i]。
5. 枚舉分割點 i，答案取 min(f1[i] + f2[i+1])。

複雜度

排序 O(N log N)，平衡樹每次操作 O(log N)，總體 O(N log N)，N ≤ 100,000 通過。