F - Count the Colors ZOJ 1610 （线段树+结点为长度为一的区间+树的遍历）

1 1

题意是区间涂色，最后问你能看见的有颜色，以及他们的段数，

真的是一道很不错的题，  这里最小的是长度为一的区间，而不是一个点，还有再次用到延迟标记，

统计段数就是对树的遍历，同时tmp记录下当前节点的先驱结点的颜色，用于判断，颜色的段数，

//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=8011;
const int inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M,R
#define M ((L+R)>>1)
#define For(i,n) for(int i=0;i<(n);i++)
template<class T>inline T read(T&x)
{
    char c;
    while((c=getchar())<=32);
    bool ok=false;
    if(c=='-')ok=true,c=getchar();
    for(x=0; c>32; c=getchar())
        x=x*10+c-'0';
    if(ok)x=-x;
    return x;
}
template<class T> inline void read_(T&x,T&y)
{
    read(x);
    read(y);
}
template<class T> inline void read__(T&x,T&y,T&z)
{
    read(x);
    read(y);
    read(z);
}
template<class T> inline void write(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{
    write(x);
    putchar('\n');
}
//-------IO template------
typedef long long  LL;

struct node
{
    int color;//-1 表示区间没有涂色， -2表示区间涂的是混合色
} p[maxn<<3];

void build(int rt,int L,int R)
{
    p[rt].color=-1;
    if(R-L==1)return ;
    build(lson);
    build(rson);
}

int cnt[maxn];
void update(int rt,int L,int R,int x,int y,int color)
{
    if(L==R||p[rt].color==color)return ;
    if(L==x&&y==R)
    {
        p[rt].color=color;
        return ;
    }
    if(p[rt].color>=0)
    {
        p[rt<<1].color=p[rt<<1|1].color=p[rt].color;
        p[rt].color=-2;
    }
    if(L<=x&&y<=M)
        update(lson,x,y,color);
    else if(x>=M&&y<=R)
        update(rson,x,y,color);
    else
    {
        update(lson,x,M,color);
        update(rson,M,y,color);
    }
    p[rt].color=-2;
}

void solve(int rt,int L,int R,int& tmp)
{
    if(p[rt].color==-1)
    {
        tmp=-1;
        return ;
    }
    if(p[rt].color>=0)
    {
        if(tmp!=p[rt].color)
        {
            tmp=p[rt].color;
            cnt[p[rt].color]++;
        }
        return ;
    }
    if(L+1!=R)
    {
        solve(lson,tmp);
        solve(rson,tmp);
    }
}
int main()
{
    int n;
    // freopen("in.txt","r",stdin);
    while(~scanf("%d",&n))
    {
        build(1,0,8000);
        int M1=0;
        For(i,n)
        {
            int left,right,color;
            read__(left,right,color);
            update(1,0,8000,left,right,color);
            M1=max(M1,color);
        }
        memset(cnt,0,sizeof(cnt));
        int tmp=-1;
        solve(1,0,8000,tmp);
        for(int i=0; i<=M1; i++)if(cnt[i])
                printf("%d %d\n",i,cnt[i]);
        printf("\n");

    }
    return 0;
}

F - Count the Colors ZOJ 1610 （线段树+结点为长度为一的区间+树的遍历）

原文：http://blog.csdn.net/u013167299/article/details/44904039