#include  < stdio.h >
#include 
< stdlib.h >
#include 
< algorithm >
#define  single(x) ( ( (x)&( (x)-1 ) )== 0 )

struct   Node
{
    
int  left,right,colour;
    Node
*  lchild,  * rchild;
}
;

Node
*  create( Node *  t,  int  a,  int  b )
{
    t
=   new  Node;
    
    t
-> left =  a; t -> right =  b; t -> colour =   1 ;
    t
-> lchild =  NULL; t -> rchild =  NULL;
    
    
if ( a <  b ) {
        t
-> lchild =  create( t -> lchild, a, (a + b) / 2  );
        t
-> rchild =  create( t -> rchild, (a + b) / 2 + 1 , b );
    }
    
    
return  t;
}


void  insert( Node *  root,  int  a, int  b,  int  c )
{
    
if ( root -> left ==  a  &&  root -> right ==  b  ||  root -> colour ==  c )
    
{
        root
-> colour =  c;
        
return ;
    }


    
if ( single(root -> colour ) )
    
{
        root
-> lchild -> colour = root -> colour;
        root
-> rchild -> colour = root -> colour;
    }

    
    
int  middle =  (root -> left +  root -> right) /   2 ;
    
    
if ( b <=  middle )      insert( root -> lchild, a, b, c );
    
else   if ( a >  middle )  insert( root -> rchild, a, b, c );
    
else {
        insert( root
-> lchild, a, middle, c );
        insert( root
-> rchild, middle +   1 , b, c );
    }

    
    
if ( root -> lchild  &&  root -> rchild )
    root
-> colour =  root -> lchild -> colour  |  root -> rchild -> colour;
}


void  getcout( Node *  root,  int  a,  int  b,  int &  cnt )
{
    
if ( root -> left ==  a  &&  root -> right ==  b  ||  single(root -> colour ) )
    
{
        cnt
=  cnt | root -> colour;
        
return ;
    }

    
    
int  middle =  (root -> left +  root -> right) /   2 ;
    
    
if ( b <=  middle )       getcout( root -> lchild, a, b, cnt );
    
else   if ( a >  middle )   getcout( root -> rchild, a, b, cnt );
    
else {
        getcout( root
-> lchild, a, middle,    cnt );
        getcout( root
-> rchild, middle +   1 , b, cnt );
    }

}


int  count(  int  i )
{
    
int  ans =   0 ;
    
while ( i >   0  )
    
{
        
if ( i & 1  ) ans ++ ;
        i
>>= 1 ;
    }

    
return  ans;
}

        
int  main()
{
    Node
*  root;
    
int  l, t, o;
    
    scanf(
" %d%d%d " , & l, & t, & o );
    root
=  create( root,  1 ,l );
    
    
char  str[ 5 ];
    
for int  i =   0 ; i <  o;  ++ i )
    
{
        scanf(
" %s " ,str);
        
        
if ( str[ 0 ] ==   ' C '  )
        
{
            
int  x, y, z;
            scanf(
" %d%d%d " , & x, & y, & z);
            
            
if ( x >  y ) std::swap(x,y);
            insert( root, x, y, 
1 << (z -   1 ) );
        }

        
else   if ( str[ 0 ] ==   ' P '  )
        
{
            
int  x, y,cnt =   0 ;
            scanf(
" %d%d " , & x, & y);
            
if ( x >  y ) std::swap(x,y);
            
            getcout( root, x, y, cnt );
            printf(
" %d\n " , count(cnt) );
        }

    }


    
return   0 ;
}

posted on 2008-10-12 12:45 Darren 阅读(253) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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