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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3159: 决战(Link Cut Tree)  

2014-06-12 17:04:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


首先如果没有权值翻转的操作的话,暴力LCT无压力,但是现在多了权值翻转,而且翻转的时候不能影响到结构,那么我们不能在原lct的splay上打标记,于是神奇的做法来了,对于lct上的每一棵splay,另外对应一棵splay来维护权值,那么每次就直接在权值splay上标记就可以了,这样就没问题啦。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  •  

  • #define clear( x ) memset( x , 0 , sizeof( x ) )

  •  

  • const int maxn = 50100 , inf = 0x7fffffff ;

  • typedef long long ll ;

  •  

  • int n , m , root ;

  •  

  • int lc[ maxn ] , rc[ maxn ] , sz[ maxn ] , fa[ maxn ] , ic[ maxn ] , va[ maxn ] , mx[ maxn ] , mn[ maxn ] ;

  • bool tr[ maxn ] ;

  • ll sm[ maxn ] ;

  •  

  • inline void Init_splay(  ) {

  •     clear( lc ) , clear( rc ) , clear( sz ) , clear( fa ) , clear( sm ) , clear( ic ) , clear( va ) , clear( mx ) , clear( tr ) ;

  •     REP( i , 0 , n ) mn[ i ] = inf ;

  • }

  •  

  • inline void make( int v ) {

  •     sz[ v ] = 1 , va[ v ] = mx[ v ] = mn[ v ] = 0 ;

  • }

  •  

  • inline void pushdown( int t ) {

  •     if ( t ) {

  •         if ( tr[ t ] ) {

  •             swap( lc[ t ] , rc[ t ] ) ;

  •             tr[ lc[ t ] ] ^= true , tr[ rc[ t ] ] ^= true , tr[ t ] = false ;

  •         }

  •         if ( ic[ t ] ) {

  •             sm[ t ] += ll( ic[ t ] ) * ll( sz[ t ] ) ;

  •             va[ t ] += ic[ t ] , mx[ t ] += ic[ t ] , mn[ t ] += ic[ t ] ;

  •             ic[ lc[ t ] ] += ic[ t ] , ic[ rc[ t ] ] += ic[ t ] ;

  •             ic[ t ] = 0 ;

  •         }

  •     }

  • }

  •  

  • inline void update( int t ) {

  •     pushdown( t ) ; pushdown( lc[ t ] ) , pushdown( rc[ t ] ) ;

  •     sz[ t ] = sz[ lc[ t ] ] + sz[ rc[ t ] ] + 1 ;

  •     sm[ t ] = sm[ lc[ t ] ] + sm[ rc[ t ] ] + ll( va[ t ] ) ;

  •     mx[ t ] = max( max( mx[ lc[ t ] ] , mx[ rc[ t ] ] ) , va[ t ] ) ;

  •     mn[ t ] = min( min( mn[ lc[ t ] ] , mn[ rc[ t ] ] ) , va[ t ] ) ;

  • }

  •  

  • inline void zag( int t ) {

  •     pushdown( t ) ; pushdown( rc[ t ] ) ;

  •     int k = rc[ t ] , u = fa[ t ] ; bool flag = ( t == lc[ fa[ t ] ] ) ;

  •     update( fa[ rc[ t ] = lc[ k ] ] = t ) ;

  •     update( fa[ lc[ k ] = t ] = k ) ;

  •     if ( fa[ k ] = u ) if ( flag ) lc[ u ] = k ; else rc[ u ] = k ;

  • }

  •  

  • inline void zig( int t ) {

  •     pushdown( t ) ; pushdown( lc[ t ] ) ;

  •     int k = lc[ t ] , u = fa[ t ] ; bool flag = ( t == lc[ fa[ t ] ] ) ;

  •     update( fa[ lc[ t ] = rc[ k ] ] = t ) ;

  •     update( fa[ rc[ k ] = t ] = k ) ;

  •     if ( fa[ k ] = u ) if ( flag ) lc[ u ] = k ; else rc[ u ] = k ;

  • }

  •  

  • inline int select( int s , int t ) {

  •     for ( pushdown( t ) ; ; ) {

  •         if ( s == sz[ lc[ t ] ] ) return t ;

  •         if ( s > sz[ lc[ t ] ] ) {

  •             s -= ( sz[ lc[ t ] ] + 1 ) ;

  •             pushdown( t = rc[ t ] ) ;

  •         } else pushdown( t = lc[ t ] ) ;

  •     }

  • }

  •  

  • inline void splay( int t , int &rt ) {

  •     while ( fa[ t ] ) {

  •         pushdown( fa[ fa[ t ] ] ) ; pushdown( fa[ t ] ) ; pushdown( t ) ;

  •         if ( ! fa[ fa[ t ] ] ) if ( t == lc[ fa[ t ] ] ) zig( fa[ t ] ) ; else zag( fa[ t ] ) ; else {

  •             if ( t == lc[ fa[ t ] ] ) {

  •                 if ( fa[ t ] == lc[ fa[ fa[ t ] ] ] ) zig( fa[ fa[ t ] ] ) ;

  •                 zig( fa[ t ] ) ;

  •             } else {

  •                 if ( fa[ t ] == rc[ fa[ fa[ t ] ] ] ) zag( fa[ fa[ t ] ] ) ;

  •                 zag( fa[ t ] ) ;

  •             }

  •         }

  •     }

  •     rt = t ;

  • }

  •  

  • inline int Max( int t ) {

  •     for ( pushdown( t ) ; rc[ t ] ; pushdown( t = rc[ t ] ) ) ;

  •     return t ;

  • }

  •  

  • #define C( t ) ( t == L( F( t ) ) )

  •  

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define S( t ) size[ t ]

  • #define F( t ) father[ t ]

  • #define G( t ) F( F( t ) )

  • #define P( t ) parent[ t ]

  • #define T( t ) bst[ t ]

  •  

  • int left[ maxn ] , right[ maxn ] , father[ maxn ] , size[ maxn ] , parent[ maxn ] , bst[ maxn ] ;

  •  

  • inline void Init_lct(  ) {

  •     clear( left ) , clear( right ) , clear( father ) , clear( size ) , clear( parent ) , clear( bst ) ;

  • }

  •  

  • inline void Pushdown( int t ) {

  •     if ( t ) {

  •         P( L( t ) ) = P( R( t ) ) = P( t ) ;

  •         T( L( t ) ) = T( R( t ) ) = P( t ) ;

  •     }

  • }

  •  

  • inline void Update( int t ) {

  •     if ( t ){

  •         Pushdown( t ) ; Pushdown( L( t ) ) , Pushdown( R( t ) ) ;

  •         S( t ) = S( L( t ) ) + S( R( t ) ) + 1 ;

  •     }

  • }

  •  

  • inline void Zag( int t ) {

  •     Pushdown( t ) ; Pushdown( R( t ) ) ;

  •     int k = R( t ) , u = F( t ) ; bool flag = C( t ) ;

  •     P( k ) = P( t ) , T( k ) = T( t ) ;

  •     Update( F( R( t ) = L( k ) ) = t ) ;

  •     Update( F( L( k ) = t ) = k ) ;

  •     if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  • }

  •  

  • inline void Zig( int t ) {

  •     Pushdown( t ) ; Pushdown( L( t ) ) ;

  •     int k = L( t ) , u = F( t ) ; bool flag = C( t ) ;

  •     P( k ) = P( t ) , T( k ) = T( t ) ;

  •     Update( F( L( t ) = R( k ) ) = t ) ;

  •     Update( F( R( k ) = t ) = k ) ;

  •     if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  • }

  •  

  • inline void Splay( int t ) {

  •     while ( F( t ) ) {

  •         Pushdown( G( t ) ) ; Pushdown( F( t ) ) ; Pushdown( t ) ;

  •         if ( ! G( t ) ) if ( C( t ) ) Zig( F( t ) ) ; else Zag( F( t ) ) ; else {

  •             if ( C( t ) ) {

  •                 if ( C( F( t ) ) ) Zig( G( t ) ) ;

  •                 Zig( F( t ) ) ;

  •             } else {

  •                 if ( ! C( F( t ) ) ) Zag( G( t ) ) ;

  •                 Zag( F( t ) ) ;

  •             }

  •         }

  •     }

  • }

  •  

  • int cnt = 0 ;

  •  

  • inline int Access( int t ) {

  •     int v = 0 ;

  •     do {

  •         Splay( t ) ;

  •         splay( select( S( L( t ) ) , T( t ) ) , T( t ) ) ; pushdown( T( t ) ) ;

  •         F( R( t ) ) = 0 , P( R( t ) ) = t ;

  •         fa[ rc[ T( t ) ] ] = 0 , T( R( t ) ) = rc[ T( t ) ] ;

  •         T( 0 ) = 0 ;

  •         update( fa[ rc[ T( t ) ] = T( v ) ] = T( t ) ) ;

  •         Update( F( R( t ) = v ) = t ) ;

  •         v = t ; t = P( t ) ;

  •     } while ( t ) ;

  •     return v ;

  • }

  •  

  • struct edge {

  •     edge *next ;

  •     int t ;

  • } E[ maxn << 1 ] ;

  •  

  • edge *pt = E , *head[ maxn ] ;

  •  

  • inline void Init_edge(  ) {

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

  • }

  •  

  • inline void add( int s , int t ) {

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

  •     head[ s ] = pt ++ ;

  • }

  •  

  • inline void addedge( int s , int t ) {

  •     add( s , t ) , add( t , s ) ;

  • }

  •  

  • int h[ maxn ] ;

  •  

  • void dfs( int v , int u ) {

  •     size[ v ] = 1 , bst[ v ] = v , make( v ) ;

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

  •         h[ p -> t ] = h[ v ] + 1 , P( p -> t ) = v ;

  •         dfs( p -> t , v ) ;

  •     }

  • }

  •  

  • inline void inc( int x , int y , int d ) {

  •     if ( h[ x ] < h[ y ] ) swap( x , y ) ;

  •     Access( x ) ;

  •     Splay( y ) ; splay( select( S( L( y ) ) , T( y ) ) , T( y ) ) ; pushdown( T( y ) ) ;

  •     ic[ rc[ T( y ) ] ] += d , va[ T( y ) ] += d ; update( T( y ) ) ;

  • }

  •  

  • inline void inv( int x , int y ) {

  •     if ( h[ x ] < h[ y ] ) swap( x , y ) ;

  •     Access( x ) ;

  •     Splay( y ) ; splay( select( S( L( y ) ) , T( y ) ) , T( y ) ) ; pushdown( T( y ) ) ;

  •     if ( lc[ T( y ) ] ) {

  •         splay( Max( lc[ T( y ) ] ) , T( y ) ) ; pushdown( T( y ) ) ;

  •         tr[ rc[ T( y ) ] ] ^= true ;

  •     } else tr[ T( y ) ] ^= true ;

  • }

  •  

  • inline ll query( int x , int y , int ty ) {

  •     Access( x ) ; int lca = Access( y ) ;

  •     if ( lca == x ) {

  •         Splay( x ) ; splay( select( S( L( x ) ) , T( x ) ) , T( x ) ) ;

  •         pushdown( T( x ) ) ; pushdown( rc[ T( x ) ] ) ;

  •         if ( ! ty ) return ll( va[ T( x ) ] ) + sm[ rc[ T( x ) ] ] ;

  •         if ( ty == 1 ) return max( va[ T( x ) ] , mx[ rc[ T( x ) ] ] ) ;

  •         return min( va[ T( x ) ] , mn[ rc[ T( x ) ] ] ) ;

  •     } else {

  •         Splay( x ) ;

  •         Splay( lca ) ; splay( select( S( L( lca ) ) , T( lca ) ) , T( lca ) ) ;

  •         pushdown( T( lca ) ) ; pushdown( rc[ T( lca ) ] ) ;

  •         if ( ! ty ) return sm[ T( x ) ] + sm[ rc[ T( lca ) ] ] + ll( va[ T( lca ) ] ) ;

  •         if ( ty == 1 ) return max( mx[ T( x ) ] , max( mx[ rc[ T( lca ) ] ] , va[ T( lca ) ] ) ) ;

  •         return min( mn[ T( x ) ] , min( mn[ rc[ T( lca ) ] ] , va[ T( lca ) ] ) ) ;

  •     }

  • }

  •  

  • int main(  ) {

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

  •     Init_splay(  ) , Init_lct(  ) , Init_edge(  ) ;

  •     REP( i , 2 , n ) {

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

  •         addedge( s , t ) ;

  •     }

  •     h[ root ] = 1 , P( root ) = 0 ; dfs( root , 0 ) ;

  •     char str[ 20 ] ;

  •     int a , b , c ;

  •     while ( m -- ) {

  •         scanf( "%s" , str ) ;

  •         if ( str[ 0 ] == 'I' ) {

  •             if ( str[ 2 ] == 'c' ) {

  •                 scanf( "%d%d%d" , &a , &b , &c ) ; inc( a , b , c ) ;

  •             } else {

  •                 scanf( "%d%d" , &a , &b ) ; inv( a , b ) ;

  •             }

  •         } else if ( str[ 0 ] == 'S' ) {

  •             scanf( "%d%d" , &a , &b ) ; printf( "%lld\n" , query( a , b , 0 ) ) ;

  •         } else {

  •             if ( str[ 1 ] == 'a' ) {

  •                 scanf( "%d%d" , &a , &b ) ; printf( "%lld\n" , query( a , b , 1 ) ) ;

  •             } else {

  •                 scanf( "%d%d" , &a , &b ) ; printf( "%lld\n" , query( a , b , 2 ) ) ;

  •             }

  •         }

  •     }

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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