POJ 2777 Count Color：線段樹 + 位掩碼維護區間顏色種數

問題描述

長度 L 的木板，初始全為顏色 1。兩種操作：
C a b c：將區間 [a,b] 塗成顏色 c。
Q a b：查詢區間 [a,b] 有多少種不同顏色。
顏色種數 T ≤ 30，操作數 O ≤ 10⁵，L ≤ 10⁵。

核心技術：線段樹 + 位掩碼

因 T ≤ 30，可用 32 位整數表示顏色集合：第 i 位為 1 表示顏色 i+1 存在。
- 節點存儲 color（位掩碼）和 lazy 標記（-1 表示無，否則為統一顏色的掩碼）。
- 合併：color = left.color | right.color。
- 查詢：遞歸收集掩碼，最後統計 1 的個數（__builtin_popcount）。

關鍵操作

• 建樹：葉子節點 color = 1 << 0（顏色 1）。
• 更新：區間完全覆蓋時，直接設 color = 1 << (c-1)，打標記。下推時將標記傳給子節點。
• 查詢：區間完全覆蓋直接返回 color；否則下推後合併左右結果（按位或）。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXL = 100005;
struct Node {
    int l, r;
    int color; // 位掩碼
    int lazy;  // -1 無標記，否則為統一顏色掩碼
} seg[MAXL << 2];
void build(int id, int l, int r) {
    seg[id].l = l; seg[id].r = r;
    seg[id].color = 1; // 顏色 1 -> bit 0
    seg[id].lazy = -1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(id<<1, l, mid);
    build(id<<1|1, mid+1, r);
}
void apply(int id, int mask) {
    seg[id].color = mask;
    seg[id].lazy = mask;
}
void pushdown(int id) {
    if (seg[id].lazy != -1) {
        apply(id<<1, seg[id].lazy);
        apply(id<<1|1, seg[id].lazy);
        seg[id].lazy = -1;
    }
}
void update(int id, int l, int r, int mask) {
    if (seg[id].l == l && seg[id].r == r) {
        apply(id, mask);
        return;
    }
    pushdown(id);
    int mid = (seg[id].l + seg[id].r) >> 1;
    if (r <= mid) update(id<<1, l, r, mask);
    else if (l > mid) update(id<<1|1, l, r, mask);
    else {
        update(id<<1, l, mid, mask);
        update(id<<1|1, mid+1, r, mask);
    }
    seg[id].color = seg[id<<1].color | seg[id<<1|1].color;
}
int query(int id, int l, int r) {
    if (seg[id].l == l && seg[id].r == r) return seg[id].color;
    pushdown(id);
    int mid = (seg[id].l + seg[id].r) >> 1;
    if (r <= mid) return query(id<<1, l, r);
    if (l > mid) return query(id<<1|1, l, r);
    return query(id<<1, l, mid) | query(id<<1|1, mid+1, r);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int L, T, O;
    while (cin >> L >> T >> O) {
        build(1, 1, L);
        for (int i = 0; i < O; ++i) {
            char op; cin >> op;
            if (op == 'C') {
                int a, b, c; cin >> a >> b >> c;
                if (a > b) swap(a, b);
                update(1, a, b, 1 << (c-1));
            } else {
                int a, b; cin >> a >> b;
                if (a > b) swap(a, b);
                int mask = query(1, a, b);
                cout << __builtin_popcount(mask) << '\n';
            }
        }
    }
    return 0;
}

複雜度

• 建樹：O(L)。
• 單次更新/查詢：O(log L)。
• 總時間：O((L + O) log L)，空間 O(L)。

常見坑點

• 查詢合併時必須用按位或 (|)，不能直接賦值（否則丟失另一側顏色）。
• 輸入 a,b 可能 a > b，需 swap。
• 顏色編號 1~T 對應 bit 0~T-1。

這題是線段樹「區間賦值 + 區間查詢集合大小」的經典模板，位掩碼技巧使集合合併極快，是區間顏色統計問題的標準解法。