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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2631: tree(伍一鸣)(LCT)  

2014-02-16 21:30:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


本来是裸的LCT的说,程序写丑了T了N次,在无数次常数优化之后终于以神奇的时间A了。。。

BZOJ-2631: tree(伍一鸣)(LCT) - cjjlsdy - cjjlsdy的博客


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define maxn 100100

  • #define mod 51061

  • #define check( ch ) ( ch == '+' || ch == '-' || ch == '*' || ch == '/' || ( ch >= '0' && ch <= '9' ) )

  • #define ll unsigned int

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

  •  

  • #define L( t ) left[ t ] 

  • #define R( t ) right[ t ]

  • #define F( t ) father[ t ]

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

  • #define P( t ) parent[ splay_roof( t ) ]

  •  

  • #define V( t ) value[ t ]

  • #define sum( t ) sum[ t ]

  • #define S( t ) size[ t ]

  •  

  • #define fa( t ) flag_a[ t ]

  • #define fb( t ) flag_b[ t ]

  • #define fr( t ) flag_r[ t ]

  •  

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

  •  

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

  • ll value[ maxn ] , sum[ maxn ] , size[ maxn ] , flag_a[ maxn ] , flag_b[ maxn ] ;

  • bool flag_r[ maxn ] ;

  •  

  • void sign( int t , ll a , ll b ) {

  •     if ( ! t ) return ;

  •     fa( t ) = ( fa( t ) * a ) % mod ;

  •     fb( t ) = ( fb( t ) * a + b ) % mod ;

  • }

  •  

  • void pushdown( int t ) {

  •     if ( t ) {

  •         if ( fa( t ) != 1 || fb( t ) != 0 ) {

  •             V( t ) = ( V( t ) * fa( t ) + fb( t ) ) % mod ;

  •             sum( t ) = ( sum( t ) * fa( t ) + S( t ) * fb( t ) ) % mod ;

  •             sign( L( t ) , fa( t ) , fb( t ) ) , sign( R( t ) , fa( t ) , fb( t ) ) ;

  •             fa( t ) = 1 , fb( t ) = 0 ;

  •         }

  •         if ( fr( t ) ) {

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

  •             fr( t ) ^= true , fr( L( t ) ) ^= true , fr( R( t ) ) ^= true ;

  •         }

  •     }

  • }

  •  

  • void update( int t ) {

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

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

  •     sum( t ) = ( sum( L( t ) ) + sum( R( t ) ) + V( t ) ) % mod ;

  • }

  •  

  • void zag( int t ) {

  •     pushdown( t ) ; pushdown( R( t ) ) ;

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

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

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

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

  • }

  •  

  • void zig( int t ) {

  •     pushdown( t ) ; pushdown( L( t ) ) ;

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

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

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

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

  • }

  •  

  • 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 Min( int t ) {

  •     pushdown( t ) ;

  •     while ( L( t ) ) {

  •         pushdown( t = L( t ) ) ;

  •     }

  •     return t ;

  • }

  •  

  • int splay_roof( int t ) {

  •     splay( t ) ;

  •     return Min( t ) ;

  • }

  •  

  • int Access( int v ) {

  •     int u = 0 ;

  •     do {

  •         splay( v ) ; pushdown( v ) ;

  •         F( R( v ) ) = 0 ; P( R( v ) ) = v ;

  •         F( R( v ) = u ) = v ; update( v ) ;

  •         u = v ; v = P( v ) ;

  •     } while ( v ) ;

  •     return u ;

  • }

  •  

  • void make( int t ) {

  •     L( t ) = R( t ) = F( t ) = parent[ t ] = 0 ;

  •     V( t ) = sum( t ) = S( t ) = 1 ;

  •     fa( t ) = 1 , fb( t ) = 0 , fr( t ) = false ;

  • }

  •  

  • void Join( int v , int u ) {

  •     P( v ) = u ;

  • }

  •  

  • void Cut( int v ) {

  •     Access( v ) ;

  •     splay( v ) ; pushdown( v ) ;

  •     F( L( v ) ) = 0 ; L( v ) = 0 ; P( v ) = 0 ; update( v ) ;

  • }

  •  

  • int Roof( int v ) {

  •     Access( v ) ;

  •     return splay_roof( v ) ;

  • }

  •  

  • struct edge {

  •     edge *next ;

  •     int t ;

  • } *head[ maxn ] ;

  •  

  • void Add( int s , int t ) {

  •     edge *p = new( edge ) ;

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

  •     head[ s ] = p ;

  • }

  •  

  • int n , m , fath[ maxn ] ;

  • bool f[ maxn ] ;

  •  

  • void dfs( int v ) {

  •     f[ v ] = false ;

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

  •         fath[ p -> t ] = v ;

  •         dfs( p -> t ) ;

  •     }

  • }

  •  

  • void getint( int &t ) {

  •     int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

  •     t = ch - '0' ;

  •     for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) {

  •         t *= 10 , t += ch - '0' ;

  •     }

  • }

  •  

  • void getll( ll &t ) {

  •     int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

  •     t = ch - '0' ;

  •     for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) {

  •         t *= 10 , t += ch - '0' ;

  •     }

  • }

  •  

  • int out[ 20 ] ;

  •  

  • void putll( ll t ) {

  •     if ( ! t ) putchar( '0' ) ; else {

  •         out[ 0 ] = 0 ;

  •         for ( ; t ; t /= 10 ) out[ ++ out[ 0 ] ] = t % 10 ;

  •         for ( int i = out[ 0 ] ; i ; -- i ) putchar( '0' + out[ i ] ) ;

  •     }

  •     putchar( '\n' ) ;

  • }

  •  

  • int main(  ) {

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

  •     getint( n ) , getint( m ) ;

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

  •         int s , t ; getint( s ) , getint( t ) ;

  •         AddEdge( s , t ) ;

  •     }

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

  •     L( 0 ) = R( 0 ) = F( 0 ) = parent[ 0 ] = 0 ;

  •     S( 0 ) = V( 0 ) = sum( 0 ) = 0 ;

  •     for ( int i = 0 ; i ++ < n ; ) make( i ) ;

  •     dfs( 1 ) ;

  •     for ( int i = 2 ; i <= n ; ++ i ) P( i ) = fath[ i ] ;

  •     while ( m -- ) {

  •         int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

  •         if ( ch == '+' ) {

  •             int u , v ; ll c ; getint( u ) , getint( v ) ; getll( c ) ;

  •             Access( u ) ;

  •             int lca = Access( v ) ;

  •             splay( lca ) ; pushdown( lca ) ;

  •             ( V( lca ) += c ) %= mod ;

  •             sign( R( lca ) , 1 , c ) ;

  •             update( lca ) ;

  •             if ( lca != u ) {

  •                 splay( u ) ;

  •                 sign( u , 1 , c ) ;

  •             }

  •         } else if ( ch == '-' ) {

  •             int x , y , u , v ; getint( x ) , getint( y ) , getint( u ) , getint( v ) ;

  •             Access( x ) ;

  •             int lca = Access( y ) ;

  •             if ( lca == x ) {

  •                 Cut( y ) ;

  •                 if ( Roof( u ) == y ) {

  •                     splay( u ) ; fr( u ) ^= true ;

  •                     Join( u , v ) ;

  •                 } else {

  •                     Access( v ) ; splay( v ) ; fr( v ) ^= true ;

  •                     Join( v , u ) ;

  •                 }

  •             } else {

  •                 Cut( x ) ;

  •                 if ( Roof( u ) == x ) {

  •                     splay( u ) ; fr( u ) ^= true ;

  •                     Join( u , v ) ;

  •                 } else {

  •                     Access( v ) ; splay( v ) ; fr( v ) ^= true ;

  •                     Join( v , u ) ;

  •                 }

  •             }

  •         } else if ( ch == '*' ) {

  •             int u , v ; ll c ; getint( u ) , getint( v ) , getll( c ) ;

  •             Access( u ) ;

  •             int lca = Access( v ) ;

  •             splay( lca ) ; pushdown( lca ) ;

  •             ( V( lca ) *= c ) %= mod ;

  •             sign( R( lca ) , c , 0 ) ;

  •             update( lca ) ;

  •             if ( lca != u ) {

  •                 splay( u ) ;

  •                 sign( u , c , 0 ) ;

  •             }

  •         } else {

  •             int u , v ; getint( u ) , getint( v ) ;

  •             Access( u ) ;

  •             int lca = Access( v ) ;

  •             splay( lca ) ; pushdown( lca ) ; pushdown( R( lca ) ) ;

  •             ll ans = ( V( lca ) + sum( R( lca ) ) ) % mod ;

  •             if ( lca != u ) {

  •                 splay( u ) ; pushdown( u ) ;

  •                 ( ans += sum( u ) ) %= mod ;

  •             }

  •             putll( ans ) ;

  •         }

  •     }

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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