回顾一下LCT,容易写错的地方:
1、每次断掉Splay中的边,必须update一下父亲节点,再根据具体情况是否splay父亲节点。
2、养成没有用的值(比如当pre[u]不为0时的pnt[u])不去乱修改的习惯。
/**************************************************************
Problem: 3282
User: idy002
Language: C++
Result: Accepted
Time:2968 ms
Memory:10712 kb
****************************************************************/ #include <cstdio>
#include <utility>
#include <set>
#define N 300010
using namespace std; typedef pair<int,int> dpr; struct Lct {
int pnt[N], pre[N], son[N][], val[N], xsum[N], rtg[N]; void update( int nd ) {
xsum[nd] = val[nd];
if( son[nd][] ) xsum[nd] ^= xsum[son[nd][]];
if( son[nd][] ) xsum[nd] ^= xsum[son[nd][]];
}
void rotate( int nd, int d ) {
int p=pre[nd];
int s=son[nd][!d];
int ss=son[s][d]; son[nd][!d] = ss;
son[s][d] = nd;
if( p ) son[p][ nd==son[p][] ] = s;
else {
pnt[s]=pnt[nd];
pnt[nd] = ;
} pre[nd] = s;
pre[s] = p;
if( ss ) pre[ss] = nd; update( nd );
update( s );
}
void pushdown( int nd ) {
if( rtg[nd] ) {
int &ls=son[nd][], &rs=son[nd][];
swap(ls,rs);
if( ls ) rtg[ls] ^= ;
if( rs ) rtg[rs] ^= ;
rtg[nd] = ;
}
}
void big_push( int nd ) {
if( pre[nd] ) big_push(pre[nd]);
pushdown(nd);
}
void splay( int nd, int top= ) {
big_push( nd );
while( pre[nd]!=top ) {
int p=pre[nd];
int nl=nd==son[p][];
if( pre[p]==top ) {
rotate( p, nl );
} else {
int pp=pre[p];
int pl=p==son[pp][];
if( nl==pl ) {
rotate( pp, pl );
rotate( p, nl );
} else {
rotate( p, nl );
rotate( pp, pl );
}
}
}
}
void access( int nd ) {
int u=nd;
int v=;
while( u ) {
splay(u);
int s=son[u][];
if( s ) {
pre[s] = ;
pnt[s] = u;
}
if( v ) {
pre[v] = u;
pnt[v] = ;
}
son[u][] = v;
update(u);
v = u;
u = pnt[u];
}
splay(nd);
}
int findroot( int u ) {
while( pre[u] ) u=pre[u];
while( pnt[u] ) {
u=pnt[u];
while( pre[u] ) u=pre[u];
}
return u;
}
void makeroot( int u ) {
access(u);
rtg[u] ^= ;
}
void cut( int u, int v ) {
makeroot(u);
access(v);
pnt[u] = pre[u] = ;
son[v][] = ;
update(v);
}
void link( int u, int v ) {
makeroot(u);
makeroot(v);
pnt[u] = v;
}
int query( int u, int v ) {
makeroot(u);
access(v);
return xsum[v];
}
void modify( int u, int v ) {
access(u);
xsum[u] ^= val[u];
val[u] = v;
xsum[u] ^= val[u];
}
}T; int n, m;
set<dpr> st; int main() {
scanf( "%d%d", &n, &m );
for( int i=,w; i<=n; i++ ) {
scanf( "%d", &w );
T.modify( i, w );
}
for( int i=,opt,u,v; i<=m; i++ ) {
scanf( "%d%d%d", &opt, &u, &v );
if( opt== ) {
printf( "%d\n", T.query(u,v) );
} else if( opt== ) {
if( u>v ) swap(u,v);
if( T.findroot(u)!=T.findroot(v) ) {
st.insert( dpr(u,v) );
T.link(u,v);
}
} else if( opt== ) {
if( u>v ) swap(u,v);
if( st.count( dpr(u,v) ) ) {
st.erase( dpr(u,v) );
T.cut(u,v);
}
} else {
T.modify( u, v );
}
}
}