注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2243: [SDOI2011]染色(树链剖分+线段树)  

2014-02-02 21:08:00|  分类: 树链剖分,线段树, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2243


轻重树链剖分之后线段树维护就好了。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define left( t ) ( t << 1 )

  • #define right( t ) ( left( t ) ^ 1 )

  • #define MAXN 101000

  • #define AddEdge( s , t ) Add( s , t ) , Add( t , s )

  • #define MAXB 20

  •  

  • struct edge {

  •     int t ;

  •     edge *next ;

  • } *head[ MAXN ] ;

  •  

  • void Add( int s , int t ) {

  •     edge *p = new( edge ) ;

  •     p -> t = t , p -> next = head[ s ] ;

  •     head[ s ] = p ;

  • }

  •  

  • bool f[ MAXN ] ;

  • int size[ MAXN ] , pchild[ MAXN ] , arr[ MAXN ] , fir[ MAXN ] , h[ MAXN ] ;

  • int up[ MAXN ][ MAXB ] , B , Index = 0 ;

  • int pos[ MAXN ] ;

  •  

  • void dfs0( int v ) {

  •     f[ v ] = false , size[ v ] = 1 ;

  •     int rec = 0 ;

  •     for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {

  •         h[ p -> t ] = h[ v ] + 1 , up[ p -> t ][ 0 ] = v ;

  •         dfs0( p -> t ) ;

  •         if ( size[ p -> t ] > rec ) {

  •             rec = size[ p -> t ] , pchild[ v ] = p -> t ;

  •         }

  •         size[ v ] += size[ p -> t ] ;

  •     }

  • }

  •  

  • void dfs1( int v , int u ) {

  •     f[ v ] = false , fir[ v ] = u , arr[ pos[ v ] = ++ Index ] = v ;

  •     if ( pchild[ v ] ) {

  •         dfs1( pchild[ v ] , u ) ;

  •         for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {

  •             dfs1( p -> t , p -> t ) ;

  •         }

  •     }

  • }

  •  

  • struct Color {

  •      

  •     int num , lcol , rcol ;

  •      

  •     Color(  ) {

  •         num = 0 ;

  •     }

  •      

  •     void SWAP(  ) {

  •         swap( lcol , rcol ) ;

  •     }

  •      

  •     void Change( int col ) {

  •         num = 1 , lcol = rcol = col ;

  •     }

  •      

  • };

  •  

  • Color operator + ( const Color &x , const Color &y ) {

  •     if ( ! x.num ) return y ;

  •     if ( ! y.num ) return x ;

  •     Color ret ;

  •     ret.num = x.num + y.num - ( x.rcol == y.lcol ) ;

  •     ret.lcol = x.lcol , ret.rcol = y.rcol ;

  •     return ret ;

  • }

  •  

  • struct node {

  •     Color c ;

  •     int l , r ;

  •     int flag ;

  •     node(  ) {

  •         flag = - 1 ;

  •     }

  • } sgt[ MAXN << 2 ] ;

  •  

  • int n , m , C[ MAXN ] ;

  •  

  • void pushdown( int t ) {

  •     if ( sgt[ t ].flag != - 1 ) {

  •         sgt[ t ].c.Change( sgt[ t ].flag ) ;

  •         if ( sgt[ t ].l < sgt[ t ].r ) {

  •             sgt[ left( t ) ].flag = sgt[ t ].flag ;

  •             sgt[ right( t ) ].flag = sgt[ t ].flag ;

  •         }

  •         sgt[ t ].flag = - 1 ;

  •     }

  • }

  •  

  • void update( int t ) {

  •     pushdown( t ) ;

  •     if ( sgt[ t ].l < sgt[ t ].r ) {

  •         pushdown( left( t ) ) , pushdown( right( t ) ) ;

  •         sgt[ t ].c = sgt[ left( t ) ].c + sgt[ right( t ) ].c ;

  •     }

  • }

  •  

  • void change( int l , int r , int col , int t ) {

  •     if ( l == sgt[ t ].l && r == sgt[ t ].r ) {

  •         sgt[ t ].flag = col ; pushdown( t ) ; return ;

  •     }

  •     pushdown( t ) ;

  •     int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;

  •     if ( r <= mid ) change( l , r , col , left( t ) ) ; else

  •     if ( l > mid ) change( l , r , col , right( t ) ) ; else {

  •         change( l , mid , col , left( t ) ) ;

  •         change( mid + 1 , r , col , right( t ) ) ;

  •     }

  •     update( t ) ;

  • }

  •  

  • void Build( int l , int r , int t ) {

  •     sgt[ t ].l = l , sgt[ t ].r = r ;

  •     if ( l == r ) {

  •         sgt[ t ].c.Change( C[ arr[ l ] ] ) ; return ;

  •     }

  •     int mid = ( l + r ) >> 1 ;

  •     Build( l , mid , left( t ) ) , Build( mid + 1 , r , right( t ) ) ;

  •     update( t ) ;

  • }

  •  

  • Color query( int l , int r , int t ) {

  •     pushdown( t ) ;

  •     if ( l == sgt[ t ].l && r == sgt[ t ].r ) return sgt[ t ].c ;

  •     int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;

  •     if ( r <= mid ) return query( l , r , left( t ) ) ;

  •     if ( l > mid ) return query( l , r , right( t ) ) ;

  •     return query( l , mid , left( t ) ) + query( mid + 1 , r , right( t ) ) ;

  • }

  •  

  • void Init(  ) {

  •     memset( head , 0 , sizeof( head ) ) ;

  •     scanf( "%d%d" , &n , &m ) ;

  •     for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , &C[ i ] ) ;

  •     for ( int i = 0 ; i ++ < n - 1 ; ) {

  •         int s , t ; scanf( "%d%d" , &s , &t ) ;

  •         AddEdge( s , t ) ;

  •     }

  •     memset( f , true , sizeof( f ) ) ;

  •     memset( h , 0 , sizeof( h ) ) ;

  •     memset( up , 0 , sizeof( up ) ) ;

  •     memset( pchild , 0 , sizeof( pchild ) ) ;

  •     h[ 1 ] = 1 ;

  •     dfs0( 1 ) ;

  •     memset( f , true , sizeof( f ) ) ;

  •     dfs1( 1 , 1 ) ;

  •     B = int( log2( n ) ) + 1 ;

  •     for ( int i = 0 ; i ++ < B ; ) {

  •         for ( int j = 0 ; j ++ < n ; ) {

  •             up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;

  •         }

  •     }

  • }

  •  

  • int Lca( int u , int v ) {

  •     if ( h[ u ] < h[ v ] ) swap( u , v ) ;

  •     for ( int i = B ; i >= 0 ; -- i ) {

  •         if ( h[ up[ u ][ i ] ] >= h[ v ] ) u = up[ u ][ i ] ;

  •     }

  •     if ( u == v ) return u ;

  •     for ( int i = B ; i >= 0 ; -- i ) {

  •         if ( up[ u ][ i ] != up[ v ][ i ] ) {

  •             u = up[ u ][ i ] , v = up[ v ][ i ] ;

  •         }

  •     }

  •     return up[ u ][ 0 ] ;

  • }

  •  

  • Color Query( int v , int lca ) {

  •     Color ret ;

  •     while ( h[ v ] >= h[ lca ] ) {

  •         if ( h[ fir[ v ] ] > h[ lca ] ) {

  •             ret = query( pos[ fir[ v ] ] , pos[ v ] , 1 ) + ret ;

  •             v = up[ fir[ v ] ][ 0 ] ;

  •         } else {

  •             ret = query( pos[ lca ] , pos[ v ] , 1 ) + ret ;

  •             break ;

  •         }

  •     }

  •     return ret ;

  • }

  •  

  • void Change( int v , int lca , int col ) {

  •     while ( h[ v ] >= h[ lca ] ) {

  •         if ( h[ fir[ v ] ] > h[ lca ] ) {

  •             change( pos[ fir[ v ] ] , pos[ v ] , col , 1 ) ;

  •             v = up[ fir[ v ] ][ 0 ] ;

  •         } else {

  •             change( pos[ lca ] , pos[ v ] , col , 1 ) ; break ;

  •         }

  •     }

  • }

  •  

  • void Solve(  ) {

  •     Build( 1 , n , 1 ) ;

  •     while ( m -- ) {

  •         int ch ; for ( ch = getchar(  ) ; ch != 'Q' && ch != 'C' ; ch = getchar(  ) ) ;

  •         if ( ch == 'Q' ) {

  •             int u , v , lca ; scanf( "%d%d" , &u , &v ) ;

  •             lca = Lca( u , v ) ;

  •             Color rec = Query( u , lca ) , ret = Query( v , lca ) ;

  •             printf( "%d\n" , rec.num + ret.num - 1 ) ;

  •         } else {

  •             int u , v , col , lca ; scanf( "%d%d%d" , &u , &v , &col ) ;

  •             lca = Lca( u , v ) ;

  •             Change( u , lca , col ) , Change( v , lca , col ) ;

  •         }

  •     }

  • }

  •  

  • int main(  ) {

  •     Init(  ) ;

  •     Solve(  ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018