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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3626: [LNOI2014]LCA(离线+LCT)  

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

  下载LOFTER 我的照片书  |

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


最近没怎么发题解额。。。刷的题都太水了没办法啊。。。其实这道还是水题。。。虽然我想了好久:

首先,lca一定是z到root的链上的点,那么定义num(v)为v的子树里面属于[l,r]的节点的数目,那么答案可以化成:

ans

=num( z )*dep( z ) + ( num( fa( z ) ) - num( z ) )*( dep( z ) - 1 ) + ... + ( num( root ) - num( fa( fa( ... ( z ) ) ) ) ) * ( dep( z ) - ( dep( z ) - 1 ) )

= num( z ) + num( fa( z ) ) + ... + num( fa( fa( ... ( z ) ) ) ) + num( root ) 

就是z到root链上的num()的和,这个在线不好维护,考虑离线:

答案具有可减性,ans(l,r)=ans(1,r)-ans(1,l-1),所以拆成前缀和,然后按节点标号排序,然后把节点的权值(1)按照标号的顺序一次加入树中,同时维护所有节点的num(),然后对当前位置的拆开的询问弄个链上求和统计贡献,这个LCT维护即可,复杂度O(q log n),也可以链剖O(q log^2 n)


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

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

  •  

  • const int maxn = 50100 ;

  •  

  • typedef long long ll ;

  •  

  • struct node {

  •     node *lc , *rc , *fa , *pr ;

  •     int sz , tag , va ;

  •     ll sm ;

  • } lct[ maxn ] ;

  •  

  • node *null ;

  •  

  • inline void Init_lct(  ) {

  •     null = lct ;

  •     null -> lc = null -> rc = null -> fa = null -> pr = null ;

  •     null -> sz = null -> sm = null -> tag = null -> va = 0 ;

  • }

  •  

  • inline void pushdown( node *t ) {

  •     if ( t == null ) return ;

  •     t -> lc -> pr = t -> rc -> pr = t -> pr ;

  •     if ( t -> tag ) {

  •         t -> sm += ( ll ) t -> sz * t -> tag , t -> va += t -> tag ;

  •         t -> lc -> tag += t -> tag , t -> rc -> tag += t -> tag ;

  •         t -> tag = 0 ;

  •     }

  • }

  •  

  • inline void update( node *t ) {

  •     if ( t == null ) return ; 

  •     pushdown( t ) ; pushdown( t -> lc ) , pushdown( t -> rc ) ;

  •     t -> sz = t -> lc -> sz + t -> rc -> sz + 1 ;

  •     t -> sm = t -> lc -> sm + t -> rc -> sm + ll( t -> va ) ;

  • }

  •  

  • #define C( t ) ( t == t -> fa -> lc )

  •  

  • inline void zag( node *t ) {

  •     pushdown( t ) ; pushdown( t -> rc ) ;

  •     node *k = t -> rc , *u = t -> fa ; bool flag = C( t ) ;

  •     update( ( t -> rc = k -> lc ) -> fa = t ) ;

  •     update( ( k -> lc = t ) -> fa = k ) ;

  •     if ( ( k -> fa = u ) != null ) if ( flag ) u -> lc = k ; else u -> rc = k ;

  • }

  •  

  • inline void zig( node *t ) {

  •     pushdown( t ) ; pushdown( t -> lc ) ;

  •     node *k = t -> lc , *u = t -> fa ; bool flag = C( t ) ;

  •     update( ( t -> lc = k -> rc ) -> fa = t ) ;

  •     update( ( k -> rc = t ) -> fa = k ) ;

  •     if ( ( k -> fa = u ) != null ) if ( flag ) u -> lc = k ; else u -> rc = k ;

  • }

  •  

  • inline void splay( node *t ) {

  •     while ( t -> fa != null ) {

  •         pushdown( t -> fa -> fa ) ; pushdown( t -> fa ) ; pushdown( t ) ;

  •         if ( t -> fa -> fa == null ) if ( C( t ) ) zig( t -> fa ) ; else zag( t -> fa ) ; else {

  •             if ( C( t ) ) {

  •                 if ( C( t -> fa ) ) zig( t -> fa -> fa ) ; zig( t -> fa ) ;

  •             } else {

  •                 if ( ! C( t -> fa ) ) zag( t -> fa -> fa ) ; zag( t -> fa ) ;

  •             }

  •         }

  •     }

  • }

  •  

  • inline void Access( node *t ) {

  •     node *v = null ;

  •     do {

  •         splay( t ) ; pushdown( t ) ;

  •         t -> rc -> fa = null , t -> rc -> pr = t ;

  •         update( ( t -> rc = v ) -> fa = t ) ;

  •         v = t ; t = t -> pr ;

  •     } while ( t != null ) ;

  • }

  •  

  • inline void make( node *t ) {

  •     t -> lc = t -> rc = t -> fa = t -> pr = null ;

  •     t -> sz = 1 , t -> sm = t -> va = t -> tag = 0 ;

  • }

  •  

  • int n , q , m = 0 ;

  •  

  • struct qtype {

  •     int p , z , x , t ;

  •     inline void oper( int _p , int _z , int _x , int _t ) {

  •         p = _p , z = _z , x = _x , t = _t ;

  •     }

  •     bool operator < ( const qtype &a ) const {

  •         return p < a.p ;

  •     }

  • } que[ maxn << 1 ] ;

  •  

  • ll ans[ maxn ] ;

  •  

  • int main(  ) {

  •     Init_lct(  ) ;

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

  •     REP( i , 1 , n ) make( lct + i ) ;

  •     REP( i , 2 , n ) {

  •         int f ; scanf( "%d" , &f ) ; ( lct + i ) -> pr = lct + f + 1 ;

  •     }  

  •     REP( i , 1 , q ) {

  •         int l , r , z ; scanf( "%d%d%d" , &l , &r , &z ) ;

  •         ++ l , ++ r , ++ z ;

  •         if ( l - 1 ) que[ ++ m ].oper( l - 1 , z , -1 , i ) ;

  •         que[ ++ m ].oper( r , z , 1 , i ) ;

  •     }

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

  •     sort( que + 1 ,que + m + 1 ) ;

  •     int j = 1 ;

  •     REP( i , 1 , n ) {

  •         Access( lct + i ) ; splay( lct + i ) ; ( lct + i ) -> tag ++ ;

  •         for ( ; j <= m && que[ j ].p == i ; ++ j ) {

  •             Access( lct + que[ j ].z ) ; splay( lct + que[ j ].z ) ; pushdown( lct + que[ j ].z ) ;

  •             ans[ que[ j ].t ] += ( ll ) que[ j ].x * ( lct + que[ j ].z ) -> sm ;

  •         }

  •     }

  •     REP( i , 1 , q ) printf( "%lld\n" , ans[ i ] % ll( 201314 ) ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(10)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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