题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2843
其实这题可以启发式合并搞掉的吧。。。我偷懒写了LCT，常数大的要死。。。跑了1600ms+
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std ;
#define C( t ) ( t == L( F( t ) ) )
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define V( t ) value[ t ]
#define S( t ) sum[ t ]
#define T( t ) tag[ t ]
#define F( t ) father[ t ]
#define P( t ) parent[ t ]
#define G( t ) F( F( t ) )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define clear( x ) memset( x , 0 , sizeof( x ) )
const int maxn = 30100 ;
int left[ maxn ] , right[ maxn ] , value[ maxn ] , sum[ maxn ] , father[ maxn ] , parent[ maxn ] ;
bool tag[ maxn ] ;
inline void Init_lct( ) {
clear( left ) , clear( right ) , clear( value ) , clear( sum ) , clear( father ) , clear( parent ) , clear( tag ) ;
}
inline void pushdown( int t ) {
if ( t ) {
if ( T( t ) ) {
swap( L( t ) , R( t ) ) ;
T( L( t ) ) ^= true , T( R( t ) ) ^= true , T( t ) = false ;
}
P( L( t ) ) = P( R( t ) ) = P( t ) ;
}
}
inline void update( int t ) {
S( t ) = S( L( t ) ) + S( R( t ) ) + V( t ) ;
}
inline void zag( int t ) {
pushdown( t ) ; pushdown( R( t ) ) ;
int k = R( t ) , u = F( t ) ; bool flag = C( 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 ) ;
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 ) ) ;
}
}
}
}
inline int access( int t ) {
int v = 0 ;
do {
splay( t ) ; pushdown( t ) ;
F( R( t ) ) = 0 ; P( R( t ) ) = t ;
update( F( R( t ) = v ) = t ) ;
v = t ; t = P( t ) ;
} while ( t ) ;
return v ;
}
inline void change( int t , int v ) {
access( t ) ; splay( t ) ;
V( t ) = v ; update( t ) ;
}
inline int query( int s , int t ) {
access( s ) ; int lca = access( t ) ;
if ( lca == s ) {
splay( s ) ; pushdown( s ) ;
return V( s ) + S( R( s ) ) ;
} else {
splay( s ) ; splay( lca ) ; pushdown( t ) ;
return S( s ) + S( R( lca ) ) + V( lca ) ;
}
}
inline void Join( int s , int t ) {
splay( s ) ; P( s ) = t ;
}
inline void Link( int s , int t ) {
access( s ) ; splay( s ) ; T( s ) ^= true ; pushdown( s ) ;
Join( s , t ) ;
}
inline int root( int t ) {
access( t ) ; splay( t ) ;
for ( pushdown( t ) ; L( t ) ; pushdown( t = L( t ) ) ) ;
splay( t ) ;
return t ;
}
char s[ 20 ] ;
int n , m ;
int main( ) {
scanf( "%d" , &n ) ;
rep( i , n ) {
scanf( "%d" , &V( i ) ) ;
S( i ) = V( i ) ;
}
int a , b ;
scanf( "%d" , &m ) ;
while ( m -- ) {
scanf( "%s%d%d" , s , &a , &b ) ;
if ( s[ 0 ] == 'b' ) {
if ( root( a ) == root( b ) ) printf( "no\n" ) ; else printf( "yes\n" ) , Link( a , b ) ;
} else if ( s[ 0 ] == 'p' ) change( a , b ) ; else
if ( root( a ) == root( b ) ) printf( "%d\n" , query( a , b ) ) ; else printf( "impossible\n" ) ;
}
return 0 ;
}
网友评论