ZOJ 1610 Count the Colors：線段樹區間更新與單點查詢詳解

題目大意

有一條長度為 8000 的線段，初始顏色為 -1（無顏色）。給定 n 個塗色操作，每個操作指定區間 [x1, x2] 塗上顏色 c。所有操作完成後，從 0 到 8000 依序查詢每個點的顏色，統計每種顏色連續區段的數量並輸出。

核心資料結構：線段樹

本題需支援 區間指派更新（將整段設為同一顏色）與 單點查詢。線段樹配合 懶惰標記 可高效處理。

節點設計

• cl[rt]：該節點代表區間的統一顏色（-1 表示非統一/混合）。
• 無需 push_up，因查詢只到葉子。

關鍵操作

1. 下推標記 push_down

void push_down(int rt) {
    if (cl[rt] != -1) {           // 當前節點為純色
        cl[rt<<1]   = cl[rt];     // 左子標記
        cl[rt<<1|1] = cl[rt];     // 右子標記
        cl[rt] = -1;              // 當前節點標記清除
    }
}

2. 區間更新 update

void update(int L, int R, int color, int l, int r, int rt) {
    if (l > R || r < L) return;           // 無交集
    if (L <= l && r <= R) {               // 完全覆蓋
        cl[rt] = color;
        return;
    }
    push_down(rt);                        // 部分覆蓋需下推
    int mid = (l + r) >> 1;
    update(L, R, color, l, mid, rt<<1);
    update(L, R, color, mid+1, r, rt<<1|1);
}

3. 單點查詢 query

int query(int pos, int l, int r, int rt) {
    if (l == r) return cl[rt];            // 葉子節點
    if (cl[rt] != -1) return cl[rt];      // 當前區間純色，直接返回
    int mid = (l + r) >> 1;
    return (pos <= mid) ? query(pos, l, mid, rt<<1)
                        : query(pos, mid+1, r, rt<<1|1);
}

主流程與統計邏輯

1. 讀入測資組數，迴圈處理每組。
2. 初始化線段樹 cl[] 為 -1，統計陣列 num[] 為 0。
3. 讀入 n 個塗色操作，呼叫 update(l, r-1, c)（注意題目區間為左閉右開）。
4. 從 0 到 8000 遍歷查詢每點顏色 x = query(i)。
5. 若 x != 前一顏色 且 x >= 0，則 num[x]++（新區段起始）。
6. 最後輸出所有 num[i] > 0 的顏色與計數。

完整程式碼（含巨集簡化）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 8000;
const int MAXSIZE = MAXN * 4 + 10;
int cl[MAXSIZE], num[MAXN+1];

#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
#define root 0, MAXN, 1

void push_down(int rt) {
    if (cl[rt] != -1) {
        cl[rt<<1] = cl[rt<<1|1] = cl[rt];
        cl[rt] = -1;
    }
}
void update(int L, int R, int c, int l, int r, int rt) {
    if (l > R || r < L) return;
    if (L <= l && r <= R) { cl[rt] = c; return; }
    push_down(rt);
    int mid = (l+r)>>1;
    update(L, R, c, lson);
    update(L, R, c, rson);
}
int query(int pos, int l, int r, int rt) {
    if (l == r || cl[rt] != -1) return cl[rt];
    int mid = (l+r)>>1;
    return pos <= mid ? query(pos, lson) : query(pos, rson);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    while (cin >> n) {
        fill(cl, cl+MAXSIZE, -1);
        fill(num, num+MAXN+1, 0);
        while (n--) {
            int l, r, c; cin >> l >> r >> c;
            update(l, r-1, c, root);
        }
        int last = -1;
        for (int i = 0; i <= MAXN; ++i) {
            int cur = query(i, root);
            if (cur != last && cur >= 0) num[cur]++;
            last = cur;
        }
        for (int i = 0; i <= MAXN; ++i)
            if (num[i]) cout << i << ' ' << num[i] << '\n';
        cout << '\n';
    }
    return 0;
}

複雜度分析

• 單次更新/查詢：O(log 8000) ≈ O(13)
• 總時間：O((n + 8000) log 8000)，極易通過時限。
• 空間：O(4 * 8000) 整數陣列。

關鍵細節提醒

• 區間輸入為 [x1, x2]，實際更新 [x1, x2-1]（右開區間）。
• 查詢範圍固定 0~8000，含端點共 8001 個點。
• 顏色值可能較大，num[] 陣列需足夠大或改用 map。
• 多組測資間需完整重置陣列。