POJ 2892 Tunnel Warfare：樹狀數組 + 二分查找動態維護連通塊

問題描述

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

• D pos：摧毀村莊 pos（斷開連接）
• Q pos：查詢與 pos 連通的村莊數
• R：恢復最近被摧毀的村莊（棧式撤銷）

核心洞察

區間 [L, R] 連通 ⇔ 區間內 1 的個數 = R-L+1。用樹狀數組維護前綴和，二分查找最遠連通邊界。

算法流程

1. 初始化：所有位置置 1，add(i, 1)
2. D pos：add(pos, -1)，將 pos 壓入棧
3. R：彈棧得 pos，add(pos, 1)
4. Q pos：
   • 若 pos 本身為 0，輸出 0
   • 向右二分：找最大 re 使 sum(re)-sum(pos-1) == re-pos+1
   • 向左二分：找最小 rs 使 sum(pos)-sum(rs-1) == pos-rs+1
   • 答案 = re - rs + 1

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55555;
int c[MAXN], stk[MAXN], top, n, m;

int lowbit(int x) { return x & -x; }
void add(int x, int d) { for (; x <= n; x += lowbit(x)) c[x] += d; }
int sum(int x) { int r = 0; for (; x; x -= lowbit(x)) r += c[x]; return r; }

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        memset(c, 0, sizeof(c));
        for (int i = 1; i <= n; ++i) add(i, 1);
        top = 0;
        char op[5];
        while (m--) {
            scanf("%s", op);
            if (op[0] == 'D') {
                int pos; scanf("%d", &pos);
                if (sum(pos) - sum(pos-1) == 1) { // 僅未摧毀時操作
                    add(pos, -1);
                    stk[top++] = pos;
                }
            } else if (op[0] == 'R') {
                if (top) add(stk[--top], 1);
            } else { // Q
                int pos; scanf("%d", &pos);
                if (sum(pos) - sum(pos-1) == 0) { puts("0"); continue; }
                int l = pos, r = n, re = pos;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (sum(mid) - sum(pos-1) == mid - pos + 1) {
                        re = mid; l = mid + 1;
                    } else r = mid - 1;
                }
                l = 1; r = pos; int rs = pos;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (sum(pos) - sum(mid-1) == pos - mid + 1) {
                        rs = mid; r = mid - 1;
                    } else l = mid + 1;
                }
                printf("%d\n", re - rs + 1);
            }
        }
    }
    return 0;
}

關鍵點解析

• 樹狀數組：單點更新、區間求和 O(log n)
• 二分查找：利用前綴和單調性，找最遠連通邊界
• 棧撤銷：R 操作天然後進先出，棧完美匹配
• 邊界檢查：查詢前先判斷 pos 是否存活

複雜度

• 每次操作 O(log n)（樹狀數組 + 二分各 log n）
• 總體 O((N+M) log N)，N,M ≤ 50000 極快

對比：並查集難以支持刪除

並查集擅長合並、查找，但不支持刪除邊（摧毀村莊）。本題「撤銷」操作實為時光倒流，棧+樹狀數組是經典解法。