HDU 1540 Tunnel Warfare：線段樹區間合並維護連續區段長度

題目大意

n 個村莊成線，初始全連通。三種操作：
D x 摧毀村莊 x（斷開連接）
Q x 查詢含 x 的最大連續連通段長度
R 恢復最近一次被摧毀的村莊（棧式撤銷）

線段樹節點信息

struct Node {
    int l, r;        // 區間範圍
    int ls, rs, ms;  // 左連續長度、右連續長度、區間內最大連續長度
} seg[4*MAXN];

關鍵合並邏輯

void push_up(int k) {
    int lc = k<<1, rc = k<<1|1;
    // 左連續
    if (seg[lc].ls == seg[lc].r - seg[lc].l + 1)
        seg[k].ls = seg[lc].ls + seg[rc].ls;
    else
        seg[k].ls = seg[lc].ls;
    // 右連續
    if (seg[rc].rs == seg[rc].r - seg[rc].l + 1)
        seg[k].rs = seg[rc].rs + seg[lc].rs;
    else
        seg[k].rs = seg[rc].rs;
    // 最大連續
    seg[k].ms = max(seg[lc].ms, seg[rc].ms);
    seg[k].ms = max(seg[k].ms, seg[lc].rs + seg[rc].ls);
}

單點更新（摧毀/恢復）

void update(int k, int pos, int val) {  // val=1 連通, 0 摧毀
    if (seg[k].l == seg[k].r) {
        seg[k].ls = seg[k].rs = seg[k].ms = val;
        return;
    }
    int mid = (seg[k].l + seg[k].r) >> 1;
    if (pos <= mid) update(k<<1, pos, val);
    else update(k<<1|1, pos, val);
    push_up(k);
}

查詢：找包含 pos 的最大連續段

int query(int k, int pos) {
    if (seg[k].l == seg[k].r || seg[k].ms == 0 || seg[k].ms == seg[k].r - seg[k].l + 1)
        return seg[k].ms;
    int mid = (seg[k].l + seg[k].r) >> 1;
    if (pos <= mid) {
        if (pos >= seg[k<<1].r - seg[k<<1].rs + 1)  // 跨越左右子樹
            return seg[k<<1].rs + seg[k<<1|1].ls;
        return query(k<<1, pos);
    } else {
        if (pos <= seg[k<<1|1].l + seg[k<<1|1].ls - 1)
            return seg[k<<1].rs + seg[k<<1|1].ls;
        return query(k<<1|1, pos);
    }
}

主流程

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

複雜度分析

• 建樹：O(n)
• 單點更新：O(log n)
• 查詢：O(log n)
• 總體：O((n+m) log n)，滿足 50,000 規模。

核心技巧總結

1. 線段樹維護 ls/rs/ms 三值，合並時判斷子區間是否「滿」決定是否跨越合併。
2. 查詢時利用 rs/ls 邊界快速判斷目標位置是否在跨越區間，避免遞歸到底。
3. R 操作本質是棧，記錄摧毀順序即可 O(1) 獲取恢復位置。