zoj - 1610 - Count the Colors（线段树）

题意：在[0, 8000]上染色n次，每次染色的区间为[x1, x2]，颜色为c，问最后每种颜色有多少段（所有数字在[0, 8000]内）。

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=610

——>>对于端点x1, x2，对应成区间段[x1+1, x2]，接着就染染色，线段树处理一下就好了。。。#^_^

SF了几次，原因：n指染色次数，并非指在区间[0, n]上染色。

#include <cstdio>
#include <cstring>

using namespace std;

#define lc (o<<1)
#define rc ((o<<1)+1)

const int N = 8000;
const int maxn = (8000 + 10) << 2;

int col[maxn], a[maxn], cnt[maxn];

void build(int o, int l, int r) {
    col[o] = -1;
    if(l == r) return;
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m+1, r);
}

void pushdown(int o) {
    col[lc] = col[rc] = col[o];
    col[o] = -1;
}

void update(int o, int l, int r, int ql, int qr, int v) {
    if(ql <= l && r <= qr) {
        col[o] = v;
        return;
    }
    if(col[o] == v) return;
    if(col[o] != -1) pushdown(o);
    int m = (l + r) >> 1;
    if(ql <= m) update(lc, l, m, ql, qr, v);
    if(qr > m) update(rc, m+1, r, ql, qr, v);
}

void query(int o, int l, int r) {
    if(col[o] != -1) {
        for(int i = l; i <= r; i++) {
            a[i] = col[o];
        }
        return;
    }
    if(l == r) return;
    int m = (l + r) >> 1;
    query(lc, l, m);
    query(rc, m+1, r);
}

void solve() {
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= N; i++)     //遍历段
        if(a[i] != a[i-1])
            cnt[a[i]]++;
    for(int i = 0; i <= N; i++)     //遍历颜色
        if(cnt[i])
            printf("%d %d\n", i, cnt[i]);
}

int main()
{
    int n, x1, x2, c;
    while(scanf("%d", &n) == 1) {
        build(1, 1, N);
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d", &x1, &x2, &c);
            update(1, 1, N, x1+1, x2, c);
        }
        memset(a, -1, sizeof(a));
        query(1, 1, N);
        solve();
        puts("");
    }
    return 0;
}

zoj - 1610 - Count the Colors（线段树）

原文：http://blog.csdn.net/scnu_jiechao/article/details/18798631