动态树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 void rotate(int x) {
 34     int y = fa[x], yson = t[y][1] == x;
 35     int gy = fa[y], gyson = t[gy][1] == y, B = t[x][yson ^ 1];
 36     if (isroot(y)) t[gy][gyson] = x;
 37     t[x][yson ^ 1] = y, t[y][yson] = B;
 38     if (B) fa[B] = y;
 39     fa[y] = x, fa[x] = gy;
 40     pushup(y);
 41 }
 42 void splay(int x) {
 43     int y = x, top = 0;
 44     stk[++top] = y;
 45     while (isroot(y)) stk[++top] = fa[y], y = fa[y];
 46     while (top) pushdown(stk[top--]);
 47     while (isroot(x)) {
 48         y = fa[x], top = fa[y];
 49         if (isroot(y)) {
 50             rotate((t[y][0] == x) ^ (t[top][0] == y) ? x : y);
 51         }
 52         rotate(x);
 53     }
 54     pushup(x);
 55 }
 56 void access(int x) { 
 57     for (int y = 0; x; y = x, x = fa[x]) {
 58         splay(x), rs = y, pushup(x);
 59     }
 60 }
 61 void makeroot(int x) {
 62     access(x), splay(x), reverse(x);
 63 }
 64 int findroot(int x) {
 65     access(x), splay(x);
 66     while (ls) pushdown(x), x = ls;
 67     splay(x);
 68     return x;
 69 }
 70 void split(int x, int y) {
 71     makeroot(x);
 72     access(y), splay(y);
 73 }
 74 void link(int x, int y) {
 75     makeroot(x);
 76     if (findroot(y) != x) fa[x] = y;
 77 }
 78 void cut(int x, int y) {
 79     makeroot(x);
 80     if (findroot(y) == x && fa[y] == x && !t[y][0]) {
 81         fa[y] = t[x][1] = 0;
 82         pushup(x);
 83     }
 84 }
 85 int main () {
 86     n = read(), m = read();
 87     for (int i = 1; i <= n; i++) {
 88         val[i] = read();
 89     }
 90     while (m--) {
 91         int o = read(), x = read(), y = read();
 92         if (o == 0) {
 93             split(x, y);
 94             printf("%d\n", s[y]);
 95         } else if (o == 1) {
 96             link(x, y);
 97         } else if (o == 2) {
 98             cut(x, y);
 99         } else {
100             splay(x);
101             val[x] = y;
102         }
103     }
104     return 0;
105 }