POJ 地道戰：線段樹維護區間最大連續長度，支援摧毀/重建村莊查詢

題目大意

N 個村莊排成一線，相鄰相連。M 個事件：

• D x：摧毀第 x 村（斷開連接）
• Q x：查詢第 x 村所在連通塊大小（含自己）
• R：恢復最近一次被摧毀的村莊（堆疊式撤銷）

N, M ≤ 50,000。輸出每次查詢結果。

線段樹節點資訊

每個節點維護：

• l：區間左端點起始的最大連續 1 長度
• r：區間右端點結尾的最大連續 1 長度
• （隱含）區間長度 len = e-s+1

合併邏輯：

if (左子樹 l == 左長度)  父.l = 左長度 + 右.l;
else 父.l = 左.l;

if (右子樹 r == 右長度)  父.r = 右長度 + 左.r;
else 父.r = 右.r;

查詢邏輯

遞歸查詢位置 pos：

• 若 pos 在左子樹且落入左子樹右連續段（pos >= mid - 左.r + 1）→ 答案 = 左.r + 右.l。
• 若 pos 在右子樹且落入右子樹左連續段（pos <= mid + 右.l）→ 答案 = 右.l + 左.r。
• 否則遞歸進對應子樹。
• 葉節點若為 0（被摧毀）直接回傳 0。

完整代碼

#include 

struct Node { int l, r; } tree[200000];
int stk[50000], top, n, m;

void build(int idx, int s, int e) {
    tree[idx].l = tree[idx].r = e - s + 1;
    if (s == e) return;
    int mid = (s + e) >> 1;
    build(idx<<1, s, mid);
    build(idx<<1|1, mid+1, e);
}

void update(int idx, int s, int e, int pos, int val) { // val=0 摧毀, 1 重建
    if (s == e) { tree[idx].l = tree[idx].r = val; return; }
    int mid = (s + e) >> 1;
    if (pos <= mid) update(idx<<1, s, mid, pos, val);
    else update(idx<<1|1, mid+1, e, pos, val);
    // 合併
    if (tree[idx<<1].l == mid - s + 1) tree[idx].l = mid - s + 1 + tree[idx<<1|1].l;
    else tree[idx].l = tree[idx<<1].l;
    if (tree[idx<<1|1].r == e - mid) tree[idx].r = e - mid + tree[idx<<1].r;
    else tree[idx].r = tree[idx<<1|1].r;
}

int query(int idx, int s, int e, int pos) {
    if (s == e) return 0; // 葉節點若被查詢必為 1，但題目保證查詢時該村存在？實際若為0應返回0
    int mid = (s + e) >> 1;
    if (pos <= mid) {
        if (pos >= mid - tree[idx<<1].r + 1) return tree[idx<<1].r + tree[idx<<1|1].l;
        return query(idx<<1, s, mid, pos);
    } else {
        if (pos <= mid + tree[idx<<1|1].l) return tree[idx<<1|1].l + tree[idx<<1].r;
        return query(idx<<1|1, mid+1, e, pos);
    }
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        build(1, 1, n);
        top = 0;
        char op[2];
        while (m--) {
            scanf("%s", op);
            if (op[0] == 'D') {
                int x; scanf("%d", &x);
                stk[top++] = x;
                update(1, 1, n, x, 0);
            } else if (op[0] == 'R') {
                update(1, 1, n, stk[--top], 1);
            } else { // Q
                int x; scanf("%d", &x);
                printf("%d\n", query(1, 1, n, x));
            }
        }
    }
    return 0;
}

關鍵點總結

1. 線段樹維護「前綴最大連續 1」與「後綴最大連續 1」，合併時處理跨越中點情況。
2. R 操作為堆疊式撤銷，用陣列 stk 記錄摧毀順序。
3. 查詢利用左右子樹的連續資訊 O(log N) 定位連通塊大小。
4. 陣列大小開 4*N 保證線段樹節點足夠。