以 P3690 为例。
#include <iostream>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
namespace LCT{ // }{{{
struct Node{
Node *ls, *rs;
Node *fa;
int sum, val;
bool rev;
Node();
} nil_, *nil = &nil_;
Node::Node(){ fa = ls = rs = nil; }
void pushup(Node *x){ x->sum = x->val ^ x->ls->sum ^ x->rs->sum; }
void reverse(Node *);
void pushdown(Node *x){
if(!x->rev) return;
std::swap(x->ls, x->rs);
if(x->ls != nil) reverse(x->ls);
if(x->rs != nil) reverse(x->rs);
x->rev = 0;
}
bool is_root(Node *x){ return x->fa->ls != x && x->fa->rs != x; }
bool is_rs(Node *x){ return x->fa->rs == x; }
void rotate(Node *x){
Node *y = x->fa, *z = y->fa;
if(!is_root(y)) {
if(is_rs(y)) z->rs = x;
else z->ls = x;
}
if(is_rs(x)){
y->rs = x->ls; x->ls->fa = y;
x->ls = y;
} else {
y->ls = x->rs; x->rs->fa = y;
x->rs = y;
}
y->fa = x;
x->fa = z;
pushup(y);
pushup(x);
}
void update(Node *x){
if(!is_root(x)) update(x->fa);
pushdown(x);
}
void splay(Node *x){
update(x);
for(Node *f=x->fa; !is_root(x); rotate(x), f=x->fa){
if(!is_root(f)) rotate(is_rs(x) == is_rs(f) ? f : x);
}
}
void access(Node *x){
for(Node *p = nil; x != nil; p=x, x=x->fa){
splay(x);
x->rs = p;
pushup(x);
}
}
void reverse(Node *x){ x->rev ^= 1; }
void makeroot(Node *x){
access(x);
splay(x);
reverse(x);
}
void split(Node *x, Node *y){
makeroot(x);
access(y);
splay(y);
}
Node *findroot(Node *x){
access(x);
splay(x);
for(;;){
pushdown(x);
if(x->ls == nil) break;
x = x->ls;
}
splay(x);
return x;
}
void link(Node *x, Node *y){
makeroot(x);
if(findroot(y) != x) x->fa = y;
}
void cut(Node *x, Node *y){
split(x, y);
if(y->ls == x) x->fa = y->ls = nil;
pushup(y);
}
} // {}}}
namespace m{ // }{{{
constexpr int N = 1e5, M = 3e5;
using std::cin;
using std::cout;
using namespace LCT;
Node nds[N];
int in, im;
void work(){
cin >> in >> im;
UP(i, 0, in) cin >> nds[i].val;
UP(i, 0, im){
int op, x, y;
cin >> op >> x >> y;
x--, y--;
if(op == 0){
split(nds+x, nds+y);
cout << nds[y].sum << '\n';
} else if(op == 1){
link(nds+x, nds+y);
} else if(op == 2){
cut(nds+x, nds+y);
} else {
splay(nds+x);
y++;
nds[x].val = y;
pushup(nds+x);
}
}
}
} // {}}}
int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); m::work(); return 0;}