ZOJ1610CounttheColors（线段树区间更新）

//ZOJ 1610
#include 
#include 
#include 

using namespace std ;

int p[8010*4],lz[8010*4] ,hashh[8010*4],hash1[8101*4];

//void pushup(int rt)
//{
//    if(p[rt <<1] == p[rt <<1 | 1])
//        p[rt] = p[rt <<1] ;
//    else p[rt] = -1 ;
//}
void pushdown(int rt)
{
    if(lz[rt] != -1)
    {
        lz[rt <<1] = lz[rt <<1 | 1] = lz[rt] ;
        p[rt <<1] = p[rt <<1 | 1] = lz[rt] ;
        lz[rt] = -1 ;
    }
}
//void build(int l,int r,int rt)
//{
//    lz[rt] = -1 ;
//    if(l == r)
//    {
//        p[rt] = -1 ;
//        return ;
//    }
//    int mid = (l + r) >> 1 ;
//    build(l,mid,rt <<1) ;
//    build(mid+1,r,rt <<1 | 1) ;
//    pushup(rt) ;
//}
void update(int L,int R,int l,int r,int rt,int sc)
{
    if(l >= L && r <= R)
    {
        lz[rt] = sc ;
        p[rt] = sc ;
        return ;
    }
    pushdown(rt) ;
    int mid = (l+r) >> 1;
    if(mid >= L)
        update(L,R,l,mid,rt <<1,sc) ;
    if(mid < R)
        update(L,R,mid+1,r,rt <<1 | 1 ,sc) ;
 //   pushup(rt) ;
}
void query(int l,int r,int rt)
{
    if(l == r)
    {
        hashh[l] = p[rt] ;
        return ;
    }
    pushdown(rt) ;
    int mid = (l+r) >> 1 ;
    query(l,mid,rt <<1) ;
    query(mid+1,r,rt <<1 | 1) ;
}
void Init()
{
    memset(lz,-1,sizeof(lz)) ;
    memset(hashh,0,sizeof(hashh)) ;
    memset(hash1,0,sizeof(hash1)) ;
    memset(p,-1,sizeof(p)) ;
}
int main()
{
    int n ,x1,x2,c;
    while(cin >> n )
    {
        Init() ;
        for(int i = 0 ; i )
        {
            cin >> x1 >> x2 >> c ;
            update(x1,x2-1,0,8000,1,c) ;
        }
        query(0,8000,1) ;
        for(int i = 1 ; i <= 8000 ; i++)
        {
            if(hashh[i] != hashh[i-1])
            {
                if(hashh[i-1] != -1)
                hash1[hashh[i-1]] ++ ;
            }
        }
        if(hashh[8000] != -1)
        hash1[hashh[8000]]++ ;
        for(int i = 0 ; i <= 8000  ;i++)
        {
            if(hash1[i])
            {
                printf("%d %d\n",i,hash1[i]) ;
            }
        }
        puts("") ;
    }
    return 0 ;
}