POJ 2777 Count Color 線段樹解法詳解 (替代實作版本)

題目回顧

同 POJ 2777：木板長度 L、顏色數 T、操作數 O。操作：C A B C 染色、P A B 查詢顏色數。初始全為顏色 1。

節點結構與建樹

struct Node { int l, r, color; } tree[MAXN<<2];  // color: -1=混合, >0=單色

void build(int l, int r, int idx) {
    tree[idx] = {l, r, 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<<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);
    }
}

查詢：收集顏色標記

int vis[33];  // T ≤ 30

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 (l > mid) query(l, r, idx<<1|1);
    else if (r <= mid) query(l, r, idx<<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);
        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 {
                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;
}

兩個版本核心邏輯一致，差異在於巨集定義風格與變數命名。本題關鍵在於識別「顏色數小」特性，以陣列替代集合，並善用懶惰標記避免不必要的遞歸下探。