1 /**************************************************************  2     Problem: 3282  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:1732 ms  7     Memory:7840 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12   13 using namespace std; 14 const int N = 300005; 15   16 struct splay_node { 17   int v, res, rev; 18   int fa, son[2]; 19 } tr[N]; 20   21 int n; 22   23 inline int read() { 24   int x = 0, sgn = 1; 25   char ch = getchar(); 26   while (ch < ‘0‘ || ‘9‘ < ch) { 27     if (ch == ‘-‘) sgn = -1; 28     ch = getchar(); 29   } 30   while (‘0‘ <= ch && ch <= ‘9‘) { 31     x = x * 10 + ch - ‘0‘; 32     ch = getchar(); 33   } 34   return sgn * x; 35 } 36   37 #define lson tr[p].son[0] 38 #define rson tr[p].son[1] 39 #define Rev tr[p].rev 40 #define Res tr[p].res 41 #define V tr[p].v 42 #define Fa tr[p].fa 43 inline void update(int p) { 44   tr[0].res = 0; 45   Res = tr[lson].res ^ tr[rson].res ^ V; 46 } 47   48 inline void push_down(int p) { 49   if (p && Rev) { 50     swap(lson, rson); 51     tr[lson].rev ^= 1, tr[rson].rev ^= 1; 52     Rev = 0; 53   } 54 } 55   56 inline bool is_root(int p) { 57   return Fa == 0 || (tr[Fa].son[0] != p && tr[Fa].son[1] != p); 58 } 59   60 inline void rotate(int p) { 61   int fa = tr[p].fa, gr = tr[fa].fa; 62   int l = (tr[fa].son[1] == p), r = !l; 63   if (!is_root(fa)) tr[gr].son[tr[gr].son[1] == fa] = p; 64   tr[p].fa = gr, tr[fa].fa = p, tr[tr[p].son[r]].fa = fa; 65   tr[fa].son[l] = tr[p].son[r], tr[p].son[r] = fa; 66   update(fa), update(p); 67 } 68   69 void splay(int p) { 70   int fa, gr; 71   while (!is_root(p)) { 72     fa = tr[p].fa, gr = tr[fa].fa; 73     push_down(gr), push_down(fa), push_down(p); 74     if (!is_root(fa)) 75       if ((fa == tr[gr].son[0]) ^ (p == tr[fa].son[0])) rotate(p); 76       else rotate(fa); 77     rotate(p); 78   } 79   push_down(p); 80 } 81   82   83 void access(int p) { 84   int t; 85   for (t = 0; p; t = p, p = Fa) { 86     splay(p); 87     rson = t, update(p); 88   } 89 } 90   91 void make_root(int p) { 92   access(p), splay(p); 93   Rev ^= 1; 94 } 95   96 int find_root(int p) { 97   access(p), splay(p); 98   while (lson) { 99     push_down(p);100     p = lson;101   }102   return p;103 }104  105  106 void cut(int x, int y) {107   make_root(x);108   access(y), splay(y);109   if (tr[y].son[0] == x && tr[x].son[1] == 0)110     tr[y].son[0] = tr[x].fa = 0, update(y);111 }112  113 void link(int x, int y) {114   make_root(x);115   tr[x].fa = y;116 }117  118 int main() {119   int i, Q, oper, x, y;120   n = read(), Q = read();121   for (i = 1; i <= n; ++i)122     tr[i].v = tr[i].res = read();123   while (Q--) {124     oper = read(), x = read(), y = read();125     if (oper == 0) {126       make_root(x);127       access(y), splay(y);128       printf("%d\n", tr[y].res);129     } else if (oper == 1) {130       if (find_root(x) != find_root(y)) link(x, y);131     }132     else if (oper == 2) {133       if (find_root(x) == find_root(y)) cut(x, y);134     }135     else {136       access(x), splay(x);137       tr[x].v = y;138       update(x);139     }140   }141   return 0;142 }