题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3282
LCT的裸题吧？记得维护一个翻转标记就可以了。
代码：
rank13，还不算太渣。。。
f3d3572c11dfa9ec99b0776660d0f703918fc120.jpg.png
21a4462309f79052bf5c664f0ef3d7ca7bcbd57b.jpg.png
# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std ;
# define MAXN 300010
# 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[path_roof( t )]
# define S( t ) sum[ t ]
# define V( t ) value[ t ]
# define T( t ) tag[ t ]
# define update( t )S( t )=S(L( t ))^S(R( t ))^V( t )
# define C( t )( t ==L(F( t )))
int left[ MAXN ], right[ MAXN ], father[ MAXN ], parent[ MAXN ], sum[ MAXN ], value[ MAXN ];
bool tag[ MAXN ];
int n , m ;
void pushdown(int t ){
if( t && tag[ t ]){
swap(L( t ),R( t ));
T( t )^=true,T(L( t ))^=true,T(R( t ))^=true;
}
}
void zag(int t ){
pushdown( t );pushdown(R( t ));
int k =R( t ), u =F( t );
bool flag =C( t );
R( t )=L( k );F(L( k ))= t ;update( t );
L( k )= t ;F( 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 );
L( t )=R( k );F(R( k ))= t ;update( t );
R( k )= t ;F( 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 path_roof(int t ){
splay( t );pushdown( t );
while(L( t )){ t =L( t );pushdown( t );}
return t ;
}
int Access(int t ){
int v =0;
do{
splay( t );pushdown( t );
F(R( t ))=0;P(R( t ))= t ;R( t )= v ;F( v )= t ;update( t );
v = t ; t =P( t );
}while( t );
return v ;
}
void Init( ){
L(0)=R(0)=F(0)= parent[0]=V(0)=S(0)=0;T(0)=false;
}
void Make_tree(int t ,int v ){
L( t )=R( t )=F( t )= parent[ t ]=0;T( t )=false;
V( t )=S( t )= v ;
}
void Cut(int t ){
Access( t );splay( t );pushdown( t );
F(L( t ))=0;L( t )=0;P( t )=0;update( t );
}
void Join(int t ,int v ){
P( t )= v ;Access( t );
}
int Find_roof(int t ){
Access( t );return path_roof( t );
}
int Max(int t ){
while(R( t )) t =R( t );return t ;
}
int main( ){
scanf("%d%d",&n ,&m );
for(int i =0; i ++< n ; ){
int x ;scanf("%d",&x );
Make_tree( i , x );
}
while( m --){
int x , y , z , w0 , w1 , w2 ;scanf("%d%d%d",&z ,&x ,&y );
switch( z ){
case0:
Access( x );splay( x ); w0 =S( x );
w2 =Access( y );splay( y ); w1 =S( y );
printf("%d\n", w0 ^ w1 ^V( w2 ));
break;
case1:
if(Find_roof( x )!=Find_roof( y )){
Access( x );splay( x );T( x )^=true;
Join( x , y );
}
break;
case2:
if(Find_roof( x )==Find_roof( y )){
Access( x );splay( x );pushdown( x );
if(Max(L( x ))== y ){
Cut( x );
}else{
Access( y );splay( y );pushdown( y );
if(Max(L( y ))== x ){
Cut( y );
}
}
}
break;
case3:
Access( x );splay( x );V( x )= y ;update( x );
break;
}
}
return 0;
}
