POJ 3225 区间集合操作：線段樹維護交、並、補、差

問題描述

實現實數軸上區間集合的動態操作：

• U l r：並集 (union)，將 [l,r] 加入集合
• I l r：交集 (intersection)，保留與 [l,r] 重疊部分
• D l r：差集 (difference)，移除 [l,r] 範圍
• C l r：補集 (complement)，在 [l,r] 內翻轉（有變無、無變有），區間外全刪除
• S l r：對稱差 (symmetric difference)，在 [l,r] 內翻轉，區間外不變

輸入多行操作，最終輸出集合表示（區間列表，按格式）。坐標範圍大，需離散化。

線段樹設計

離散化

收集所有端點 l, r，以及 l-1, r+1（處理開閉區間），排序去重。將實數軸映射為基本區間 [x[i], x[i+1])。線段樹葉子對應基本區間。

懶標記：Cover + XOR

• cover[node]：-1=無覆蓋標記，0=全刪除，1=全添加
• xor[node]：0/1，表示該區間需翻轉
• 優先級：cover 覆蓋 xor。賦值操作清除 xor；xor 操作若遇 cover 則翻轉 cover，否則翻轉 xor

操作映射

關鍵代碼

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 150000;
int cover[N<<2], XOR[N<<2];
bool output[N<<2]; // 最終輸出標記

void applyXOR(int rt) {
    if (cover[rt] != -1) cover[rt] ^= 1;
    else XOR[rt] ^= 1;
}

void pushDown(int rt) {
    if (cover[rt] != -1) {
        cover[rt<<1] = cover[rt<<1|1] = cover[rt];
        XOR[rt<<1] = XOR[rt<<1|1] = 0;
        cover[rt] = -1;
    }
    if (XOR[rt]) {
        applyXOR(rt<<1); applyXOR(rt<<1|1);
        XOR[rt] = 0;
    }
}

void update(int L, int R, char op, int l, int r, int rt) {
    if (L <= l && r <= R) {
        switch(op) {
            case 'U': cover[rt]=1; XOR[rt]=0; break;
            case 'D': cover[rt]=0; XOR[rt]=0; break;
            case 'C': case 'S': applyXOR(rt); break;
            case 'I': break; // 區間內不變，區間外在下面處理
        }
        return;
    }
    pushDown(rt);
    int m = (l+r)/2;
    if (L <= m) update(L, R, op, lson);
    else if (op=='I' || op=='C') cover[rt<<1]=XOR[rt<<1]=0; // 區間外操作
    if (m < R) update(L, R, op, rson);
    else if (op=='I' || op=='C') cover[rt<<1|1]=XOR[rt<<1|1]=0;
}

void collect(int l, int r, int rt) {
    if (cover[rt] == 1) {
        for (int i=l;i<=r;++i) output[i]=true;
        return;
    }
    if (cover[rt] == 0) return;
    pushDown(rt);
    int m=(l+r)/2;
    collect(lson); collect(rson);
}

輸出格式處理

遍歷 output[] 合併連續 true 區間，根據原離散坐標還原開閉區間：離散索引奇數為開區間端點，偶數為閉區間端點（或根據具體映射規則）。格式如 [a,b]、(a,b) 等。

總結

POJ 3225 是線段樹懶標記「覆蓋 + 異或」組合的經典習題。關鍵難點在於：
1. 正確建立離散化映射處理開閉區間
2. 覆蓋標記與異或標記的優先級交互邏輯
3. 五種操作到區間內/外標記的精確映射
4. 最終結果從線段樹收集並格式化輸出
掌握此題，可處理任意區間集合的布爾運算動態維護問題。