ZOJ 1610 Count the Colors：線段樹懶標記 + 暴力統計顏色段

ZOJ 1610「Count the Colors」：在數軸上依次繪製彩色線段，後繪製覆蓋前者。最終統計每種可見顏色的線段數（連續同色算一段）。本文解析線段樹區間賦值懶標記 + 最終遍歷統計的標準解法。

問題建模

• 坐標範圍 [0, 8000]，整數端點。
• n ≤ 8000 條線段，每段 [x1, x2) 顏色 c（注意右端點開區間）。
• 後繪製覆蓋前繪製 → 區間賦值操作。
• 最終掃描全域，統計連續同色段數。

線段樹設計

• 節點存儲：color，-1 表示混合色，≥0 表示純色。
• 懶標記：tag，-1 表示無，≥0 表示整段染為該色。
• 區間 [0, 8000] 對應 8001 個單位段（或 8000 個點間隔），建樹範圍 [0, 8000]。

關鍵操作

void pushdown(int rt) {
    if (tag[rt] != -1) {
        tag[ls] = tag[rs] = tag[rt];
        color[ls] = color[rs] = tag[rt];
        tag[rt] = -1;
    }
}

void update(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && r <= R) {
        color[rt] = tag[rt] = c;
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (L <= mid) update(L, R, c, l, mid, ls);
    if (R > mid) update(L, R, c, mid+1, r, rs);
    // 內部節點不維護 color，僅葉子節點最終統計用
}

最終統計：暴力遍歷葉子

中序遍歷線段樹葉子節點，收集顏色序列 col[]，然後掃描統計連續段：

void collect(int l, int r, int rt) {
    if (l == r) {
        col[cnt++] = color[rt];
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    collect(l, mid, ls);
    collect(mid+1, r, rs);
}

// 統計
for (int i = 0; i < cnt; ) {
    int c = col[i];
    if (c != -1) ans[c]++;
    int j = i + 1;
    while (j < cnt && col[j] == c) ++j;
    i = j;
}

完整代碼框架（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXC = 8000;
const int MAXN = MAXC * 4 + 10;
int color[MAXN], tag[MAXN];
int col[MAXN], ans[MAXN];
int cnt, n;

void pushdown(int rt) { ... }
void update(int L, int R, int c, int l, int r, int rt) { ... }
void collect(int l, int r, int rt) { ... }

int main() {
    while (scanf("%d", &n) == 1) {
        cnt = 0;
        memset(tag, -1, sizeof(tag));
        memset(color, -1, sizeof(color));
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < n; ++i) {
            int x1, x2, c;
            scanf("%d%d%d", &x1, &x2, &c);
            update(x1, x2-1, c, 0, MAXC, 1); // 右端點開區間
        }
        collect(0, MAXC, 1);
        for (int i = 0; i < cnt; ) {
            int c = col[i];
            if (c != -1) ans[c]++;
            int j = i + 1;
            while (j < cnt && col[j] == c) ++j;
            i = j;
        }
        for (int c = 0; c <= 8000; ++c)
            if (ans[c]) printf("%d %d\n", c, ans[c]);
        puts("");
    }
    return 0;
}

關鍵細節

1. 右端點開區間：輸入 x1 x2 c 表示 [x1, x2)，更新時用 x2-1。
2. 坐標壓縮不需要：8000 很小，直接建樹 4×8000 節點足夠。
3. 顏色 0 有效：題目顏色為非負整數，0 也是合法顏色，統計時包含。
4. 多測試用例：EOF 結束，每用例間輸出空行。