laekov

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);

}

}

}