动态树LCT

  1 #include <bits/stdc++.h>
  2 #define ls t[x][0]
  3 #define rs t[x][1]
  4 using namespace std;
  5 const int N = 3e5 + 7;
  6 int read() {
  7     int re = 0, f = 1;
  8     char ch = getchar();
  9     while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();}
 10     while ('0' <= ch && ch <= '9') {re = re * 10 + ch - '0'; ch = getchar();}
 11     return re * f;
 12 }
 13 int n, m;
 14 bool rev[N];
 15 int t[N][2], fa[N], val[N], s[N], stk[N];
 16 bool isroot(int x) {
 17     return t[fa[x]][0] == x || t[fa[x]][1] == x;
 18 }
 19 void pushup(int x) {
 20     s[x] = s[ls] ^ s[rs] ^ val[x];
 21 }
 22 void reverse(int x) {
 23     rev[x] ^= 1;
 24     swap(ls, rs);
 25 }
 26 void pushdown(int x) {
 27     if (rev[x]) {
 28         if (ls) reverse(ls);
 29         if (rs) reverse(rs);
 30         rev[x] = 0;
 31     }
 32 }
 33 int identify(int x) {
 34     return t[fa[x]][1] == x;
 35 }
 36 void connect(int x, int father, int Son) {
 37     fa[x] = father;
 38     t[father][Son] = x;
 39 }
 40 void rotate(int x) {
 41     int y = fa[x], fason = identify(x);
 42     int gfa = fa[y], gfason = identify(y);
 43     int B = t[x][fason ^ 1];
 44     fa[x] = fa[y];
 45     if (isroot(y)) connect(x, gfa, gfason);
 46     connect(B, y, fason), connect(y, x, fason ^ 1);
 47     pushup(y), pushup(x);
 48 }
 49 void splay(int x) {
 50     int y = x, top = 0;
 51     stk[++top] = y;
 52     while (isroot(y)) stk[++top] = fa[y], y = fa[y];
 53     while (top) pushdown(stk[top--]);
 54     while (isroot(x)) {
 55         y = fa[x], top = fa[y];
 56         if (isroot(y)) {
 57             rotate((t[y][0] == x) ^ (t[top][0] == y) ? x : y);
 58         }
 59         rotate(x);
 60     }
 61     pushup(x);
 62 }
 63 void access(int x) { 
 64     for (int y = 0; x; y = x, x = fa[x]) {
 65         splay(x), rs = y, pushup(x);
 66     }
 67 }
 68 void makeroot(int x) {
 69     access(x), splay(x), reverse(x);
 70 }
 71 int findroot(int x) {
 72     access(x), splay(x);
 73     while (ls) pushdown(x), x = ls;
 74     splay(x);
 75     return x;
 76 }
 77 void split(int x, int y) {
 78     makeroot(x);
 79     access(y), splay(y);
 80 }
 81 void link(int x, int y) {
 82     makeroot(x);
 83     if (findroot(y) != x) fa[x] = y;
 84 }
 85 void cut(int x, int y) {
 86     makeroot(x);
 87     if (findroot(y) == x && fa[y] == x && !t[y][0]) {
 88         fa[y] = t[x][1] = 0;
 89         pushup(x);
 90     }
 91 }
 92 int main () {
 93     n = read(), m = read();
 94     for (int i = 1; i <= n; i++) {
 95         val[i] = read();
 96     }
 97     while (m--) {
 98         int o = read(), x = read(), y = read();
 99         if (o == 0) {
100             split(x, y);
101             printf("%d
", s[y]);
102         } else if (o == 1) {
103             link(x, y);
104         } else if (o == 2) {
105             cut(x, y);
106         } else {
107             splay(x);
108             val[x] = y;
109         }
110     }
111     return 0;
112 }