#include  < stdio.h >
#include 
< stdlib.h >
#include 
< string .h >

#define  NOC -1
#define  MUC -2
#define  N   8001
#define  M   10000

struct   Node
{
    
int   leftvalue;
    
int   rightvalue;
    
int   colour;
    
    Node
*   leftchild;
    Node
*   rightchild;
}
;
int    colour[M];

Node
*  create( Node *  r,  int  left,  int  right )
{    
    Node
*  temp =   new  Node;
    
    temp
-> leftvalue =  left;
    temp
-> rightvalue =  right;
    temp
-> colour =  NOC;
    
    temp
-> rightchild =  NULL;
    temp
-> leftchild =  NULL;
        
    
if  ( right -  left ==   1  )  return  temp;
    
else
        temp
-> leftchild =  create( temp -> leftchild, left, (left +  right) /   2  );
        temp
-> rightchild =  create( temp -> rightchild, (left + right) /   2 , right );
    }

    
    
return  temp;
}
       

void  insert( Node *  tree,  int  left,  int  right,  int  c )
{
    
int  middle =  ( tree -> leftvalue +  tree -> rightvalue ) /   2 ;
    
    
if  ( right ==  tree -> rightvalue  &&  left ==  tree -> leftvalue  ||  tree -> colour ==  c)
    
{
        tree
-> colour =   c;
        
return ;
    }
   
    
    
if  ( tree -> colour  >=   0  )
    
{
        tree
-> leftchild -> colour =  tree -> colour;
        tree
-> rightchild -> colour =  tree -> colour;
    }
    
        
    tree
-> colour =  MUC;
    
if  ( middle >=  right )       insert( tree -> leftchild, left, right, c );
    
else    if  ( middle <=  left )  insert( tree -> rightchild, left, right,c );
    
else
    
{   
        insert( tree
-> leftchild, left, middle, c );
        insert( tree
-> rightchild, middle, right, c );
    }
    
       
}
 

void  getcolour( Node *  tree,  int &  col )
{
    
if  ( tree -> colour >=   0   &&  tree -> colour !=  col )
    
{
        col
=  tree -> colour;
        colour[ tree
-> colour ] ++ ;
    }
    
    
else   if  ( tree -> colour ==  MUC )
    
{
        getcolour( tree
-> leftchild, col );
        getcolour( tree
-> rightchild, col );
    }

    
else  col =  tree -> colour;   
}
              
            
int  main()
{
    Node
*  root;
    
int    n;
    
    
while ( scanf( " %d " , & n) !=  EOF )
    
{
        root
=  create( root,  0 , N );
        
int   a, b, c;
        
for  (  int  i =   0 ; i <  n;  ++ i )
        
{
            scanf(
" %d%d%d " , & a, & b, & c);
            insert( root, a, b, c );
        }

        
        memset( colour, 
0 sizeof (colour) );
        
int  col =   - 1 ;
        getcolour( root, col );
        
        
for  (  int  i =   0 ; i <  M;  ++ i ) 
          
if  ( colour[i] ) printf( " %d %d\n " , i, colour[i] );   
        printf(
" \n " );    
    }
    
    
    
return   0 ;
}
        
posted on 2008-10-08 14:29 Darren 阅读(498) 评论(1)  编辑 收藏 引用 所属分类: 数据结构

评论:
# re: Zoj 1610 Count the Colors[未登录] 2009-04-07 19:49 | wolf
非常感谢大牛的共享 。。。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理