您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 2892 Tunnel Warfare：平衡樹維護動態連通區間查詢

編輯：關於C++

問題描述

n 個村莊（n ≤ 50,000）排成一線，相鄰村莊有隧道相連。m 個事件（m ≤ 50,000）：

D x：第 x 個村莊被摧毀（隧道斷開）
Q x：查詢第 x 個村莊所在連通塊大小（含自身）
R：恢復最近一次被摧毀的村莊（棧式撤銷）

輸出每個 Q 操作的答案。樣例中村莊 3,6,5 依次摧毀，查詢 4 輸出 1（孤立），查詢 5 輸出 0（已摧毀），恢復後查詢 4 輸出 2，再恢復查詢 4 輸出 4。

核心洞察：維護「被摧毀村莊」有序集合

村莊連通塊由「被摧毀村莊」分割。若村莊 x 未被摧毀，其所在連通塊邊界為：

左邊界：x 左側最近的被摧毀村莊（前驱）
右邊界：x 右側最近的被摧毀村莊（後繼）
連通塊大小 = 後繼 - 前驱 - 1

兩端虛擬邊界：0 和 n+1 視為永久「被摧毀」。

平衡樹操作映射

事件	平衡樹操作
D x	插入 x；壓入棧記錄撤銷順序
R	棧頂彈出 y，刪除 y
Q x	若 x 在樹中 → 輸出 0；否則查前驱 p、後繼 s，輸出 s - p - 1

Splay 核心代碼框架

const int MAXN = 50005;
int ch[MAXN][2], fa[MAXN], val[MAXN], sz[MAXN], rnd[MAXN];
bool destroyed[MAXN];
stack history;
int root = 0, tot = 0;

// 旋轉、Splay、查找第 k 大、前驱/後繼、插入、刪除
// ... 標準 Splay 實現 ...

int get_pre(int x) { // 最大的 < x
    int cur = root, ans = 0;
    while (cur) {
        if (val[cur] < x) { ans = cur; cur = ch[cur][1]; }
        else cur = ch[cur][0];
    }
    return ans ? val[ans] : 0; // 0 為左虛擬邊界
}

int get_suc(int x) { // 最小的 > x
    int cur = root, ans = 0;
    while (cur) {
        if (val[cur] > x) { ans = cur; cur = ch[cur][0]; }
        else cur = ch[cur][1];
    }
    return ans ? val[ans] : n+1; // n+1 為右虛擬邊界
}

int main() {
    n = read(); m = read();
    // 初始化：插入虛擬邊界 0 和 n+1
    insert(root, 0); insert(root, n+1);
    
    while (m--) {
        char op = read_op();
        if (op == 'D') {
            int x = read();
            destroyed[x] = true;
            history.push(x);
            insert(root, x);
        } else if (op == 'Q') {
            int x = read();
            if (destroyed[x]) printf("0\n");
            else {
                int p = get_pre(x), s = get_suc(x);
                printf("%d\n", s - p - 1);
            }
        } else { // 'R'
            int x = history.top(); history.pop();
            destroyed[x] = false;
            del(root, x);
        }
    }
}