LCT 模板

以 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;}