POJ 2777 Count Color 線段樹區間染色與查詢完整解析

題目大意

長度 L (≤ 100,000) 的木板，初始全為顏色 1。支援兩種操作 (O ≤ 100,000)：

• C A B C：將區間 [A, B] 染成顏色 C (≤ 30)
• P A B：查詢區間 [A, B] 含多少種不同顏色

顏色數 T ≤ 30 較小，適合用位元組/陣列記錄顏色集合。

線段樹節點設計

struct Node {
    int l, r;      // 區間範圍
    int color;     // -1 表示混合色，>0 表示單一顏色
} tree[400010];

int vis[35];  // 查詢時標記出現的顏色

核心操作實作

建樹

void build(int l, int r, int idx) {
    tree[idx].l = l; tree[idx].r = r;
    tree[idx].color = 1;  // 初始全為顏色 1
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, idx<<1);
    build(mid+1, r, idx<<1|1);
}

區間染色 (懶惰標記思想)

void update(int l, int r, int c, int idx) {
    if (tree[idx].color == c) return;  // 已是目標顏色，剪枝
    if (tree[idx].l == l && tree[idx].r == r) {
        tree[idx].color = c;  // 完全覆蓋，打標記
        return;
    }
    // 下推標記：若當前節點為單色，將顏色傳給子節點
    if (tree[idx].color != -1) {
        tree[idx<<1].color = tree[idx].color;
        tree[idx<<1|1].color = tree[idx].color;
        tree[idx].color = -1;  // 標記為混合色
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (l > mid) update(l, r, c, idx<<1|1);
    else if (r <= mid) update(l, r, c, idx<<1);
    else {
        update(l, mid, c, idx<<1);
        update(mid+1, r, c, idx<<1|1);
    }
}

區間查詢顏色種類數

void query(int l, int r, int idx) {
    if (tree[idx].color != -1) {  // 單色節點，直接記錄
        vis[tree[idx].color] = 1;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (r <= mid) query(l, r, idx<<1);
    else if (l > mid) query(l, r, idx<<1|1);
    else {
        query(l, mid, idx<<1);
        query(mid+1, r, idx<<1|1);
    }
}

主程式流程

int main() {
    int L, T, O;
    while (scanf("%d%d%d", &L, &T, &O) == 3) {
        build(1, L, 1);
        memset(vis, 0, sizeof(vis));
        while (O--) {
            char op; int a, b, c;
            getchar(); scanf("%c", &op);
            if (op == 'C') {
                scanf("%d%d%d", &a, &b, &c);
                if (a > b) swap(a, b);
                update(a, b, c, 1);
            } else {  // 'P'
                scanf("%d%d", &a, &b);
                if (a > b) swap(a, b);
                memset(vis, 0, sizeof(vis));
                query(a, b, 1);
                int ans = 0;
                for (int i = 1; i <= T; ++i) if (vis[i]) ++ans;
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

關鍵優化點

1. 懶惰標記不下推至葉子：區間完全覆蓋時直接打標記，避免 O(N) 更新
2. 同色剪枝：if (tree[idx].color == c) return; 避免無意義遞歸
3. 顏色數小 (≤30)：查詢用固定大小陣列 vis[35] 而非集合容器，極快

本題核心考察「區間覆蓋更新 + 區間查詢不同值個數」，線段樹懶惰標記是標準解法。注意 color = -1 表示混合色而非「無顏色」。