POJ 2892 Tunnel Warfare：線段樹維護動態連通區間長度

題目大意

n 個村莊連成一線，初始全連通。三種操作：

• D x：摧毀村莊 x (斷開連接)
• Q x：查詢 x 所在連通區間長度 (含 x)
• R：恢復最近一次摧毀的村莊 (棧式撤銷)

n, m ≤ 50000。

線段樹節點信息

每個節點維護區間 [l, r] 內：

• lmax：從左端點開始的最大連續完好段長
• rmax：從右端點開始的最大連續完好段長
• tmax：區間內最大連續完好段長 (本題查詢不直接用，但合併需要)

葉子節點：完好時 lmax=rmax=tmax=1，摧毀時 =0。

合併邏輯 (Pull)

void pushup(int rt) {
    int ls = rt<<1, rs = rt<<1|1;
    tmax[rt] = max({tmax[ls], tmax[rs], rmax[ls] + lmax[rs]});
    lmax[rt] = lmax[ls];
    if (lmax[ls] == mid - l + 1)  // 左子區間全完好
        lmax[rt] += lmax[rs];
    rmax[rt] = rmax[rs];
    if (rmax[rs] == r - mid)  // 右子區間全完好
        rmax[rt] += rmax[ls];
}

查詢邏輯

查詢位置 x 所在連通段長度：

int query(int rt, int l, int r, int x) {
    if (l == r) return 0;  // 葉子長度 1，但邏輯中已處理
    int mid = (l+r)>>1;
    if (x <= mid) {
        if (x >= mid - rmax[rt<<1] + 1)  // x 在左子區間右端完好段內
            return rmax[rt<<1] + lmax[rt<<1|1];
        else
            return query(rt<<1, l, mid, x);
    } else {
        if (x <= mid + lmax[rt<<1|1])  // x 在右子區間左端完好段內
            return lmax[rt<<1|1] + rmax[rt<<1];
        else
            return query(rt<<1|1, mid+1, r, x);
    }
}

完整代碼 (精簡版)

#include 
#include 
using namespace std;

const int MAXN = 50000;
int lmax[MAXN*4], rmax[MAXN*4], tmax[MAXN*4];
int stk[MAXN], top;
int n, m;

void build(int rt, int l, int r) {
    lmax[rt] = rmax[rt] = tmax[rt] = r - l + 1;
    if (l == r) return;
    int mid = (l+r)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
}

void update(int rt, int l, int r, int pos, int val) {
    if (l == r) { lmax[rt] = rmax[rt] = tmax[rt] = val; return; }
    int mid = (l+r)>>1;
    if (pos <= mid) update(rt<<1, l, mid, pos, val);
    else update(rt<<1|1, mid+1, r, pos, val);
    // pushup 同前
}

int query(int rt, int l, int r, int pos) {
    if (l == r) return 0;
    int mid = (l+r)>>1;
    if (pos <= mid) {
        if (pos >= mid - rmax[rt<<1] + 1) return rmax[rt<<1] + lmax[rt<<1|1];
        return query(rt<<1, l, mid, pos);
    } else {
        if (pos <= mid + lmax[rt<<1|1]) return lmax[rt<<1|1] + rmax[rt<<1];
        return query(rt<<1|1, mid+1, r, pos);
    }
}

int main() {
    char op[5];
    while (~scanf("%d%d", &n, &m)) {
        build(1, 1, n);
        top = 0;
        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;
}

關鍵設計點

複雜度分析

• 構建：O(n)
• 更新/查詢：O(log n)
• 總計：O((n+m) log n)，n,m≤50000 時 < 0.1s
• 空間：O(4n) 整數數組

線段樹維護區間連續屬性通用模式

1. 定義節點信息：前綴/後綴/區間最值
2. 實現 pushup 合併邏輯 (處理跨中點情況)
3. 更新：單點修改 + 向上 pushup
4. 查詢：遞歸下沉 + 利用兄弟節點信息計算跨段答案

適用於：最大連續子段和、最長連續 1、括號匹配長度、顏色段長度等問題。

總結

POJ 2892 是線段樹維護動態連通區間的經典題。核心技巧：三值維護 (lmax/rmax/tmax) + 查詢時跨段合併 + 棧式撤銷。此模式可擴展到區間翻轉、區間賦值等懶標記操作，是線段樹進階應用的基礎範本。