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

U - Count the Colors：區間染色與顏色區間統計（線段樹成段更新）

編輯：C++ 入門

問題描述

給定 n 個操作，每個操作定義為 x1, x2, c，表示將區間 [x1, x2] 染成顏色 c。區間可以重複染色，最終需要統計每種顏色在畫布上形成了多少個不連續的區間。注意：這裡的操作對象是區間而非單個點。

核心思路：線段樹成段更新 + 統計映射

這道題的關鍵在於利用線段樹的「成段更新」特性高效處理區間染色，並在最後將線段樹的節點信息映射到一個陣列中進行統計，而非試圖直接在線段樹上統計每種顏色的區間數——這是一個關鍵的轉折點。

線段樹結構設計

線段樹節點包含左右邊界 l、r 和顏色標記 col。col = -1 表示該節點區間內顏色不統一（混合狀態），col >= 0 表示該區間被整體染成某種顏色。

成段更新操作

更新時，若當前節點區間完全被操作區間覆蓋，直接打標記；否則下推標記（若有），遞歸更新左右子節點。這保證了區間染色的時間複雜度為 O(log N)。

統計階段：樹映射到陣列

所有操作完成後，通過一次遍歷將線段樹的顏色信息「推平」到一個陣列 arr[] 中，其中 arr[i] 表示第 i 個單位長度區間的最終顏色。然後掃描該陣列：每當 arr[i] != arr[i-1] 時，說明顏色發生變化，對應顏色的區間計數加一。首個區間單獨計數。

代碼實現要點

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int maxn = 8010;
struct node {
    int l, r;
    int col;
} tree[maxn * 4];
int ans[maxn];
int arr[maxn];

void build(int v, int l, int r) {
    tree[v].l = l;
    tree[v].r = r;
    tree[v].col = -1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
}

void update(int v, int l, int r, int col) {
    if (tree[v].l == l && tree[v].r == r) {
        tree[v].col = col;
        return;
    }
    if (tree[v].col != -1) {
        tree[v * 2].col = tree[v * 2 + 1].col = tree[v].col;
        tree[v].col = -1;
    }
    int mid = (tree[v].l + tree[v].r) >> 1;
    if (r <= mid) update(v * 2, l, r, col);
    else if (l > mid) update(v * 2 + 1, l, r, col);
    else {
        update(v * 2, l, mid, col);
        update(v * 2 + 1, mid + 1, r, col);
    }
}

void query(int v, int l, int r) {
    if (tree[v].col != -1) {
        for (int i = tree[v].l; i <= tree[v].r; i++) {
            arr[i] = tree[v].col;
        }
        return;
    }
    if (tree[v].l == tree[v].r) {
        arr[tree[v].l] = tree[v].col;
        return;
    }
    int mid = (tree[v].l + tree[v].r) >> 1;
    if (r <= mid) query(v * 2, l, r);
    else if (l > mid) query(v * 2 + 1, l, r);
    else {
        query(v * 2, l, mid);
        query(v * 2 + 1, mid + 1, r);
    }
}

int main() {
    int n, cn, t;
    int ll[maxn], rr[maxn], cc[maxn];
    while (~scanf("%d", &t)) {
        memset(ans, 0, sizeof(ans));
        n = -1;
        cn = -1;
        for (int i = 1; i <= t; i++) {
            scanf("%d %d %d", &ll[i], &rr[i], &cc[i]);
            n = max(n, rr[i]);
            cn = max(cn, cc[i]);
        }
        build(1, 0, n - 1);
        for (int i = 1; i <= t; i++) {
            update(1, ll[i], rr[i] - 1, cc[i]);
        }
        query(1, 0, n - 1);
        ans[arr[0]] += 1;
        for (int i = 1; i <= n - 1; i++) {
            if (arr[i] != arr[i - 1]) ans[arr[i]] += 1;
        }
        for (int i = 0; i <= cn; i++) {
            if (ans[i]) printf("%d %d\n", i, ans[i]);
        }
        printf("\n");
    }
    return 0;
}