您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

ZOJ 1610 Count the Colors：線段樹區間染色統計

編輯：關於C++

問題描述

在 [0, 8000] 區間上進行多次區間染色操作，每次指定區間 [a, b] 染為顏色 c。最終統計每種顏色形成的連續區段數量。注意：相鄰同色區間若不連續（如 [1,2] 和 [3,4]）算作兩段。

線段樹懶標記設計

節點存儲 color：-1 表示混合色，≥0 表示純色
區間完全覆蓋時直接打標記，無需遞歸到底
下推操作：父節點純色時將顏色傳給兩子節點

離散化技巧：避免相鄰區間合併

為區分 [1,2] 和 [3,4] 這類邊界相鄰但不重疊的區間，將所有端點 ×2 處理：

原區間 [a, b] 映射為 [2a, 2b]
相鄰區間間隔至少 2，中間留出間隙
查詢時只檢查偶數位置

核心代碼實現

const int MAXN = 8000 * 2 + 10;
int color[MAXN << 2];

void pushdown(int rt) {
    if (color[rt] != -1) {
        color[rt<<1] = color[rt<<1|1] = color[rt];
        color[rt] = -1;
    }
}

void update(int L, int R, int rt, int l, int r, int c) {
    if (l <= L && R <= r) { color[rt] = c; return; }
    pushdown(rt);
    int mid = (L + R) >> 1;
    if (l <= mid) update(L, mid, rt<<1, l, r, c);
    if (r > mid) update(mid+1, R, rt<<1|1, l, r, c);
}

void query(int L, int R, int rt, vector<int>& res) {
    if (color[rt] != -1) {
        for (int i = L; i <= R; ++i) res[i] = color[rt];
        return;
    }
    if (L == R) return;
    int mid = (L + R) >> 1;
    query(L, mid, rt<<1, res);
    query(mid+1, R, rt<<1|1, res);
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        fill(color, color + (MAXN<<2), -1);
        int maxColor = 0;
        for (int i = 0; i < n; ++i) {
            int a, b, c; scanf("%d%d%d", &a, &b, &c);
            if (a > b) continue;
            maxColor = max(maxColor, c);
            update(1, 16000, 1, a*2, b*2, c); // 離散化×2
        }
        vector<int> finalColor(16001);
        query(1, 16000, 1, finalColor);
        
        vector<int> cnt(maxColor + 1, 0);
        for (int i = 2; i <= 16000; i += 2) { // 只看偶數位
            if (finalColor[i] == -1) continue;
            int c = finalColor[i];
            while (i <= 16000 && finalColor[i] == c) i += 2;
            cnt[c]++;
            i -= 2;
        }
        for (int c = 0; c <= maxColor; ++c)
            if (cnt[c]) printf("%d %d\n", c, cnt[c]);
        puts("");
    }
}