LCT的简单题。好久不写都手生了，还把rotate写错了一点点，导致找了半天错。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_s_) {\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxn = 300009;
int n, m;
int ls[maxn], rs[maxn], pt[maxn], rv[maxn], vl[maxn], vs[maxn];
inline void update(const int& p) {
vs[p] = vs[ls[p]] ^ vl[p] ^ vs[rs[p]];
}
inline void fix(int p) {
if (rv[p]) {
swap(ls[p], rs[p]);
if (ls[p])
rv[ls[p]] ^= 1;
if (rs[p])
rv[rs[p]] ^= 1;
rv[p] = 0;
}
}
inline void lRot(int q) {
int p = pt[q], a = pt[p];
if (a) {
if (p == ls[a])
ls[a] = q;
else if (p == rs[a])
rs[a] = q;
}
if (rs[q])
pt[rs[q]] = p;
ls[p] = rs[q];
rs[q] = p;
pt[q] = a;
pt[p] = q;
update(p);
update(q);
}
inline void rRot(int q) {
int p = pt[q], a = pt[p];
if (a) {
if (p == ls[a])
ls[a] = q;
else if (p == rs[a])
rs[a] = q;
}
if (ls[q])
pt[ls[q]] = p;
rs[p] = ls[q];
ls[q] = p;
pt[q] = a;
pt[p] = q;
update(p);
update(q);
}
inline bool isRoot(int p) {
return !pt[p] || (p != ls[pt[p]] && p != rs[pt[p]]);
}
void splay(int q) {
static int stc[maxn];
int tst = 1, r = q;
stc[tst] = q;
while (!isRoot(q)) {
stc[++ tst] = pt[q];
q = pt[q];
}
while (tst)
fix(stc[tst --]);
q = r;
while (!isRoot(q)) {
int p = pt[q], a = pt[p];
if (isRoot(p)) {
if (q == ls[p])
lRot(q);
else
rRot(q);
}
else {
if (p == ls[a]) {
if (q == ls[p])
lRot(p), lRot(q);
else
rRot(q), lRot(q);
}
else {
if (q == ls[p])
lRot(q), rRot(q);
else
rRot(p), rRot(q);
}
}
}
}
int expose(int q) {
int p = 0;
for (; q; q = pt[q]) {
splay(q);
fix(q);
rs[q] = p;
update(q);
p = q;
}
fix(p);
while (ls[p]) {
p = ls[p];
fix(p);
}
return p;
}
void makeRoot(int p) {
expose(p);
splay(p);
rv[p] ^= 1;
}
void link(int u, int v) {
if (expose(u) == expose(v))
return;
makeRoot(u);
pt[u] = v;
}
void cut(int u, int v) {
makeRoot(u);
expose(v);
splay(v);
fix(v);
if (ls[v] != u)
return;
pt[u] = 0;
ls[v] = 0;
update(v);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(m);
vl[0] = 0;
vs[0] = 0;
for (int i = 1; i <= n; ++ i) {
readInt(vl[i]);
vs[i] = vl[i];
ls[i] = 0;
rs[i] = 0;
pt[i] = 0;
rv[i] = 0;
}
while (m --) {
int opt, x, y;
readInt(opt);
readInt(x);
readInt(y);
if (opt == 0) {
makeRoot(x);
expose(y);
splay(y);
printf("%d\n", vs[y]);
}
else if (opt == 1) {
link(x, y);
}
else if (opt == 2) {
cut(x, y);
}
else if (opt == 3) {
splay(x);
vl[x] = y;
update(x);
}
}
}