BZOJ-2843: 极地旅行社（Link Cut Tree）

题目：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 ;

}