ZOJ 3511 Cake Robbery - 線段樹區間查詢/刪除維護多邊形切割

題目大意

n 邊凸多邊形，切 m 刀 (對角線)，保證切割線不相交。每刀切去一塊，問切割過程中出現的最大邊數的子多邊形邊數。

關鍵觀察：按切割大小排序模擬

不相交對角線形成樹狀結構。切去頂點數較少的那側，該側完全被包含在另一側內。故可按切去頂點數升序處理：小塊先切，切去的頂點從多邊形中移除，剩餘頂點用線段樹維護。

線段樹維護頂點集合

• 葉節點：1 表示頂點存在，0 表示已切去。
• 節點值 sum：區間內存在頂點數。
• 支援：區間查詢 sum、區間賦 0 (切去)。

演算法流程

1. 讀入 m 條切割線 (l, r)，確保 l < r，頂點數 = r - l + 1 (含端點)。
2. 按 r - l 升序排序 (切去較小側優先)。
3. 初始化線段樹 (全 1)。
4. 遍歷切割線：

ans = max(ans, query(l, r)); // 當前塊頂點數
add(l+1, r-1);               // 切去內部頂點 (端點保留為相鄰塊邊界)

完整代碼

#include 
using namespace std;
const int MAXN = 10005;

struct Query { int l, r; };
Query q[MAXN];
int n, m;

struct Node { int l, r, sum, lazy; } tr[MAXN*4];

void build(int u, int l, int r) { /* 標準建樹 sum=1 */ }
void pushdown(int u) { if (tr[u].lazy) { tr[ls].lazy=tr[rs].lazy=1; tr[ls].sum=tr[rs].sum=0; tr[u].lazy=0; } }
void update(int u, int l, int r) { /* 區間賦 0 */ }
int query(int u, int l, int r) { /* 區間求和 */ }

int main() {
    while (cin >> n >> m) {
        for (int i = 0; i < m; ++i) {
            cin >> q[i].l >> q[i].r;
            if (q[i].l > q[i].r) swap(q[i].l, q[i].r);
        }
        sort(q, q+m, [](Query a, Query b) { return a.r - a.l < b.r - b.l; });
        build(1, 1, n);
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            ans = max(ans, query(1, q[i].l, q[i].r));
            if (q[i].l + 1 <= q[i].r - 1)
                update(1, q[i].l + 1, q[i].r - 1);
        }
        ans = max(ans, tr[1].sum);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 排序：O(m log m)。
• 線段樹操作：O(m log n)。
• 總計：O((n+m) log n)。

關鍵細節

• 切割線端點保留 (l+1, r-1)：端點為相鄰子多邊形共用頂點，不可刪除。
• 按切割大小排序保證小塊先切，大塊查詢時小塊頂點已移除，查詢結果正確。