HDU 1540 Tunnel Warfare 線段樹區間合併詳解（另一版本實現與註釋）

HDU 1540 Tunnel Warfare 線段樹區間合併詳解（另一版本實現與註釋）

本文提供 HDU 1540 的另一版本線段樹實現，採用 ls/rs/ms 命名與 InitTree/UpdataTree/SearchTree 函數結構，邏輯與前文一致，但代碼風格與註釋細節不同，適合對比學習。

節點結構與建樹

struct node {
    int l, r;
    int ls, rs, ms; // 左連續、右連續、區間最大連續
} s[50050 * 3];

void InitTree(int l, int r, int k) {
    s[k].l = l; s[k].r = r;
    s[k].ls = s[k].rs = s[k].ms = r - l + 1; // 初始全連通
    if (l == r) return;
    int mid = (l + r) >> 1;
    InitTree(l, mid, k << 1);
    InitTree(mid + 1, r, k << 1 | 1);
}

單點更新：摧毀/修復

void UpdataTree(int x, int flag, int k) {
    if (s[k].l == s[k].r) {
        if (flag == 1) s[k].ls = s[k].rs = s[k].ms = 1; // 修復
        else s[k].ls = s[k].rs = s[k].ms = 0;           // 摧毀
        return;
    }
    int mid = (s[k].l + s[k].r) >> 1;
    if (x <= mid) UpdataTree(x, flag, k << 1);
    else UpdataTree(x, flag, k << 1 | 1);
    
    // 向上合併
    if (s[k<<1].ls == s[k<<1].r - s[k<<1].l + 1)
        s[k].ls = s[k<<1].ls + s[k<<1|1].ls;
    else s[k].ls = s[k<<1].ls;
    
    if (s[k<<1|1].rs == s[k<<1|1].r - s[k<<1|1].l + 1)
        s[k].rs = s[k<<1|1].rs + s[k<<1].rs;
    else s[k].rs = s[k<<1|1].rs;
    
    s[k].ms = max(max(s[k<<1].ms, s[k<<1|1].ms), s[k<<1].rs + s[k<<1|1].ls);
}

區間查詢：定位 x 所在連通段長度

int SearchTree(int x, int k) {
    if (s[k].l == s[k].r || s[k].ms == 0 || s[k].ms == s[k].r - s[k].l + 1)
        return s[k].ms;
    
    int mid = (s[k].l + s[k].r) >> 1;
    if (x <= mid) {
        // x 在左子樹，若落在左子樹右連續段，需合併右子樹左段
        if (x >= s[k<<1].r - s[k<<1].rs + 1)
            return s[k<<1].rs + s[k<<1|1].ls; // 等價於 SearchTree(x,k<<1)+SearchTree(mid+1,k<<1|1)
        else
            return SearchTree(x, k<<1);
    } else {
        // x 在右子樹，對稱判斷
        if (x <= s[k<<1|1].l + s[k<<1|1].ls - 1)
            return s[k<<1].rs + s[k<<1|1].ls;
        else
            return SearchTree(x, k<<1|1);
    }
}

主流程與堆疊回滾

int main() {
    int n, m, x; char ch[2];
    while (~scanf("%d%d", &n, &m)) {
        int top = 0, op[50010];
        InitTree(1, n, 1);
        while (m--) {
            scanf("%s", ch);
            if (ch[0] == 'D') {
                scanf("%d", &x);
                op[top++] = x;
                UpdataTree(x, 0, 1);
            } else if (ch[0] == 'Q') {
                scanf("%d", &x);
                printf("%d\n", SearchTree(x, 1));
            } else { // R
                if (top > 0) {
                    x = op[--top];
                    UpdataTree(x, 1, 1);
                }
            }
        }
    }
    return 0;
}

關鍵點對比表

兩版本本質相同，版本二查詢函數少一次遞歸調用，常數級優化；版本一結構更模組化。建議初學者先理解版本一邏輯，再體會版本二優化技巧。