BZOJ 2300 【HAOI2011】防線修建：動態凸包離線解法

問題建模

給定河邊兩點 (0,0)、(n,0) 及首都 (x,y) 必須保護，另有 m 個可選城市。操作有刪除城市保護和詢問最小防線長度（凸包周長扣除河邊）。河邊為 x 軸，所有城市 y > 0，x ∈ (0,n)。

核心洞察：離線 + 逆向插入

動態凸包刪點極難，但刪除操作可逆向轉化為「加點」。將所有操作記錄，標記被刪除的城市，先構建最終狀態的凸包（僅含未被刪除的點），再按操作逆序處理：遇詢問記錄當前答案，遇刪除（逆向為加點）將點插入凸包並維護周長。

凸包維護關鍵技術

• 用 set<Point> 按 x 坐標排序維護凸包頂點（上凸包）。
• 插入新點時，用 lower_bound 找左右鄰居，判斷新點是否在現有凸包內（向量叉積判斷）。
• 若在外側，向左右擴展，刪除被新點「蓋過」的舊頂點（叉積判斷凸性），更新周長變量 now。
• 周長初始為 (0,0)→首都→(n,0) 兩段距離之和。

向量運算輔助

struct Point { int x, y; };
Point operator-(Point a, Point b) { return {a.x-b.x, a.y-b.y}; }
long long cross(Point a, Point b) { return 1LL*a.x*b.y - 1LL*a.y*b.x; }
double dist(Point a, Point b) { return sqrt(1.0*(a.x-b.x)*(a.x-b.x) + 1.0*(a.y-b.y)*(a.y-b.y)); }

複雜度

每點插入/刪除均攤 O(log m)，總時間 O((m+q) log m)，空間 O(m+q)，滿足 m ≤ 10⁵, q ≤ 2×10⁵。