POJ 2777 Count Color - 線段樹區間覆蓋更新與顏色查詢

問題描述

長度 L ≤ 100000 的木板，初始顏色 1。兩種操作：C A B C 將區間 [A,B] 塗成顏色 C；P A B 查詢區間 [A,B] 不同顏色數。顏色總數 T ≤ 30，操作數 O ≤ 100000。

線段樹 + 位掩碼

每個節點維護：

• cover：若整段同色，存顏色編號 (1..T)；否則 0 表示混合。
• 查詢時遍歷樹，遇到 cover > 0 直接將該顏色標記在 bool vis[31] 中，不再遞歸子節點。

更新：區間覆蓋打標記 cover = C，下推時將標記傳給子節點。由於 T ≤ 30，也可用 32 位整數位掩碼表示顏色集合，合併用按位或，查詢統計位數。但打標記 + 訪問數組更簡單高效。

複雜度

每次操作 O(log L)，總 O(O log L)，空間 O(L)。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100010;

int cover[MAXN<<2];
bool vis[35];
int L, T, O;

void build(int o, int l, int r) {
    cover[o] = 1;
    if (l == r) return;
    int m = (l+r)>>1;
    build(o<<1, l, m);
    build(o<<1|1, m+1, r);
}

void pushDown(int o) {
    if (cover[o]) {
        cover[o<<1] = cover[o<<1|1] = cover[o];
        cover[o] = 0;
    }
}

void update(int o, int l, int r, int L, int R, int c) {
    if (L <= l && r <= R) { cover[o] = c; return; }
    pushDown(o);
    int m = (l+r)>>1;
    if (L <= m) update(o<<1, l, m, L, R, c);
    if (R > m) update(o<<1|1, m+1, r, L, R, c);
}

void query(int o, int l, int r, int L, int R, int& ans) {
    if (cover[o]) {
        if (!vis[cover[o]]) { vis[cover[o]] = true; ++ans; }
        return;
    }
    int m = (l+r)>>1;
    if (L <= m) query(o<<1, l, m, L, R, ans);
    if (R > m) query(o<<1|1, m+1, r, L, R, ans);
}

int main() {
    while (scanf("%d%d%d", &L, &T, &O) == 3) {
        build(1, 1, L);
        char op[2];
        int A, B, C;
        while (O--) {
            scanf("%s%d%d", op, &A, &B);
            if (A > B) swap(A, B);
            if (op[0] == 'C') {
                scanf("%d", &C);
                update(1, 1, L, A, B, C);
            } else {
                memset(vis, 0, sizeof(vis));
                int ans = 0;
                query(1, 1, L, A, B, ans);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}