POJ 2777 Count Color：線段樹維護顏色集合（位掩碼優化）

問題描述

長度 L（≤10⁵）木板，初始顏色 1。T 種顏色（T≤30），O 次操作（O≤10⁵）：

• C A B C：區間 [A,B] 塗顏色 C
• P A B：查詢區間 [A,B] 不同顏色數

位掩碼技巧

T≤30，用 32 位整數每位代表一種顏色（bit 0 代表顏色 1，...）。區間顏色集合 = 位或運算。查詢顏色數 = 統計 1 的個數（__builtin_popcount）。

線段樹節點信息

• col[rt]：若整段同色，存顏色掩碼（1<<(c-1)）；否則 -1 表示混色
• sum[rt]：該區間顏色掩碼（所有顏色的或）

關鍵操作

// 下推：將同色標記傳給子節點
void pushdown(int rt) {
    if (col[rt] != -1) {
        col[rt<<1] = col[rt<<1|1] = col[rt];
        sum[rt<<1] = sum[rt<<1|1] = col[rt];
        col[rt] = -1;
    }
}

// 上傳：合併子節點顏色集合
void pushup(int rt) {
    sum[rt] = sum[rt<<1] | sum[rt<<1|1];
}

// 區間塗色
void update(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && r <= R) {
        col[rt] = sum[rt] = (1 << (c-1));
        return;
    }
    pushdown(rt);
    int mid = (l+r)>>1;
    if (L <= mid) update(L, R, c, l, mid, rt<<1);
    if (R > mid) update(L, R, c, mid+1, r, rt<<1|1);
    pushup(rt);
}

// 區間查詢顏色掩碼
int query(int L, int R, int l, int r, int rt) {
    if (col[rt] != -1) return col[rt];  // 整段同色，直接返回
    if (L <= l && r <= R) return sum[rt];
    pushdown(rt);  // 必須下推，否則子節點 col 可能過期
    int mid = (l+r)>>1, res = 0;
    if (L <= mid) res |= query(L, R, l, mid, rt<<1);
    if (R > mid) res |= query(L, R, mid+1, r, rt<<1|1);
    return res;
}

完整代碼

#include 
using namespace std;
const int MAXN = 100005;

int col[MAXN<<2], sum[MAXN<<2];

void build(int l, int r, int rt) {
    col[rt] = sum[rt] = 1;  // 初始顏色 1 -> bit 0
    if (l == r) return;
    int mid = (l+r)>>1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int L, T, O;
    while (cin >> L >> T >> O) {
        build(1, L, 1);
        while (O--) {
            char op; cin >> op;
            if (op == 'C') {
                int a, b, c; cin >> a >> b >> c;
                if (a > b) swap(a, b);
                update(a, b, c, 1, L, 1);
            } else {
                int a, b; cin >> a >> b;
                if (a > b) swap(a, b);
                int mask = query(a, b, 1, L, 1);
                cout << __builtin_popcount(mask) << '\n';
            }
        }
    }
    return 0;
}

關鍵點總結

複雜度

• 構建：O(L)
• 單次操作：O(log L)
• 總計：O((L+O) log L)，空間 O(L)

避坑指南

• 顏色編號 1-based，掩碼用 1<<(c-1)
• 輸入 A 可能 > B，需 swap
• 初始化 col[rt]=sum[rt]=1（顏色 1）
• query 中遇到 col[rt]!=-1 直接返回，不要忘記這一步優化