HDU 1540 Tunnel Warfare：線段樹維護動態連通區間

題目背景

地道戰問題：n 個村莊排成一線，相鄰村莊由地道連接。m 次操作：

• D x：摧毀第 x 個村莊（地道斷開）；
• Q x：查詢包含第 x 村莊的最大連通區間長度（含自身）；
• R：恢復上一次被摧毀的村莊（棧式撤銷）。

輸出每次查詢的結果。n, m ≤ 50,000。

線段樹節點信息設計

每個節點維護三個關鍵值，對應區間 [l, r]：

• ls：左端點起始的最長連續完好段長度（前綴長度）；
• rs：右端點結束的最長連續完好段長度（後綴長度）；
• ms：區間內的最長連續完好段長度（最大子段長度）。

葉子節點初始 ls = rs = ms = 1（完好），摧毀後置 0。

合併邏輯（PushUp）

void pushUp(int idx) {
    Node &cur = tree[idx], &lc = tree[idx<<1], &rc = tree[idx<<1|1];
    cur.ls = lc.ls;
    cur.rs = rc.rs;
    cur.ms = max({lc.ms, rc.ms, lc.rs + rc.ls});
    // 若左子區間全完好，前綴可延伸至右子區間前綴
    if (lc.ls == lc.r - lc.l + 1) cur.ls += rc.ls;
    // 若右子區間全完好，後綴可延伸至左子區間後綴
    if (rc.rs == rc.r - rc.l + 1) cur.rs += lc.rs;
}

查詢邏輯

查詢位置 x 所在的最大連通長度，遞歸下降：

• 若當前節點區間全完好或全摧毀，直接返回 ms；
• 若 x 在左子區間：
   - 若 x 落在左子區間的右後綴內（即 x >= lc.r - lc.rs + 1），需合併左子區間後綴與右子區間前綴；
   - 否則遞歸查詢左子區間。
• 若 x 在右子區間：邏輯對稱。

撤銷操作（R）

利用棧記錄每次 D 操作的村莊索引，R 時彈棧並調用更新函數將該位置恢復為 1。

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50000 + 10;

struct Node {
    int l, r;
    int ls, rs, ms;
} tree[MAXN << 2];

int stk[MAXN], top;

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

void update(int pos, int idx, int val) { // val=1 恢復, 0 摧毀
    if (tree[idx].l == tree[idx].r) {
        tree[idx].ls = tree[idx].rs = tree[idx].ms = val;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (pos <= mid) update(pos, idx<<1, val);
    else update(pos, idx<<1|1, val);
    pushUp(idx);
}

int query(int pos, int idx) {
    if (tree[idx].l == tree[idx].r || tree[idx].ms == 0 || tree[idx].ms == tree[idx].r - tree[idx].l + 1)
        return tree[idx].ms;
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (pos <= mid) {
        if (pos >= tree[idx<<1].r - tree[idx<<1].rs + 1)
            return query(pos, idx<<1) + query(mid+1, idx<<1|1);
        else
            return query(pos, idx<<1);
    } else {
        if (pos <= tree[idx<<1|1].l + tree[idx<<1|1].ls - 1)
            return query(pos, idx<<1|1) + query(mid, idx<<1);
        else
            return query(pos, idx<<1|1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        top = 0;
        build(1, n, 1);
        char op[2];
        int x;
        while (m--) {
            cin >> op;
            if (op[0] == 'D') {
                cin >> x;
                stk[top++] = x;
                update(x, 1, 0);
            } else if (op[0] == 'Q') {
                cin >> x;
                cout << query(x, 1) << '\n';
            } else { // R
                if (top > 0) {
                    x = stk[--top];
                    update(x, 1, 1);
                }
            }
        }
    }
    return 0;
}

複雜度分析

• 建樹：O(n)
• 單次更新/查詢：O(log n)
• 總時間：O((n + m) log n)，滿足限制。
• 空間：O(n)。