BZOJ-3626: [LNOI2014]LCA（离线+LCT）
2019-03-15 本文已影响0人
AmadeusChan
题目：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 ;
}
