ZOJ 1610 Count the colors(Segment tree)

Description

给区间涂色（可遮挡），问最终可看到哪几种颜色，以及这几种颜色分别有几段？

Analyze

跟POJ有一道“贴海报”的题类似，只不过那题只求最终可以看到几种海报，这题还要统计段数。暴力单点查询，用一个last变量记录上一个点的颜色，若与现在这个点颜色不相同，那当前颜色段数++。更新last。

Code

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 8005;

int n, cnt[N], last = -1;
struct interval
{
    int L, R, val;
} a[N << 2 | 1];

void init(int num, int l, int r)
{
    a[num].L = l;
    a[num].R = r;
    a[num].val = -1;

    if(l == r)
        return ;

    int mid = (l + r) >> 1;
    init(num << 1, l, mid);
    init(num << 1 | 1, mid + 1, r);
}

void down(int x)
{
    if(a[x].val != -1)
    {
        a[x << 1].val = a[x].val;
        a[x << 1 | 1].val = a[x].val;
        a[x].val = -1;
    }
}

void update(int num, int l, int r, int t)
{
    if(a[num].L > r || a[num].R < l)
        return ;
    if(a[num].L >= l && a[num].R <= r)
    {
        a[num].val = t;
        return ;
    }
    if(a[num].L == a[num].R)///in case of endless recursion
        return ;

    down(num);
    update(num << 1, l, r, t);
    update(num << 1 | 1, l, r, t);
}

void query(int num, int l, int r)
{
    if(a[num].L == a[num].R)///in case of endless recursion
    {
        if(a[num].val != -1 && a[num].val != last)
            cnt[ a[num].val ]++;
        last = a[num].val;///Even it's empty(without any color).
        return ;
    }
    down(num);
    query(num << 1, l, r);
    query(num << 1 | 1, l, r);
}

int main()
{
    int L, R, idx;
    while(~scanf("%d", &n))
    {
        last = -1;
        init(1, 1, 8000);
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0; i < n; ++i)
        {
            scanf("%d %d %d", &L, &R, &idx);
            update(1, L + 1, R, idx);
        }
        query(1, 1, 8000);
        for(int i = 0; i <= 8000; ++i)
            if(cnt[i] > 0)
                cout << i << ' ' << cnt[i] << '\n';
        cout << '\n';
    }
    return 0;
}