#include  < iostream >
#include 
< cstdio >
#include 
< cstdlib >
#include 
< cstring >

using   namespace  std;

int  L, T, O;
int  tb[ 300000 ] =  { 0 };
void  insert(  int  l,  int  r,  int  a,  int  b,  int  rt,  int  c ){
    
if ( l ==  a  &&  r ==  b ){
        tb[rt]
=  c;  return ; }
    
if ( tb[rt] >   0  ){
        tb[rt
<< 1 ] =  tb[rt], tb[(rt << 1 ) + 1 ] =  tb[rt]; tb[rt] =   0 ; }
    
int  m =  (l +  r) >>   1 ;
    
if ( b <=  m ) insert( l, m, a, b, rt <<   1 , c );
    
else   if ( a >  m ) insert( m +   1 , r, a, b, (rt << 1 ) +   1 , c );
    
else  {
        insert( l, m, a, m, rt
<<   1 , c );
        insert( m
+   1 , r, m +   1 , b, (rt << 1 ) +   1 , c ); }
}
void  query(  int  l,  int  r,  int  a,  int  b,  int  rt,  int &  ans ){
    
if ( l ==  a  &&  r ==  b  &&  tb[rt] >   0  ){
        ans
|=  ( 1 << tb[rt]);  return ;  }
    
if ( tb[rt] >   0  ){
        tb[rt
<< 1 ] =  tb[rt], tb[(rt << 1 ) + 1 ] =  tb[rt]; }
    
int  m =  (l +  r) >>   1 ;
    
if ( b <=  m ) query( l, m, a, b, rt <<   1 , ans );
    
else   if ( a >  m ) query( m +   1 , r, a, b, (rt << 1 ) +   1 , ans );
    
else {
        query( l, m, a, m, rt
<<   1 , ans );
        query( m
+   1 , r, m +   1 , b, (rt << 1 ) +   1 , ans ); }
}
int  getnum(  int  t ){
    
int  ans =   0 ;
    
for int  i =   1 ; i <=  T;  ++ i )
    
if ( t &  ( 1 << i ) ) ans ++ ;
    
return  ans;}

int  main(){
    scanf(
" %d%d%d " , & L,  & T,  & O );
    tb[
1 ] =   1 ;
    
char  str[ 5 ];
    
int  a, b, c, d;
    
while ( O --  ){
        scanf(
" %s " , str );
        
if ( str[ 0 ] ==   ' C '  ){
            scanf(
" %d%d%d " , & a, & b, & c );
            
if ( a >  b ) { d =  a; a =  b; b =  d; }
            insert( 
1 , L, a, b,  1 , c );
        }
        
else {
            scanf(
" %d%d " , & a, & b ); c =   0 ;
            
if ( a >  b ) { d =  a; a =  b; b =  d; }
            query( 
1 , L, a, b,  1 , c );
            printf(
" %d\n " , getnum(c) );
        }
    }
    
return   0 ;
}
posted on 2009-07-14 10:50 Darren 阅读(304) 评论(1)  编辑 收藏 引用 所属分类: 数据结构

评论:
# re: Pku 2777 Count Color 2010-07-21 09:37 | Dereky
太牛了,用位来标识颜色,太猛了
太佩服了  回复  更多评论
  

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