论什么是LCT？蒟蒻也不造。。。
splay写错是shen me gui = =
话说，要注意翻转标记！！！
还是要注意link & cut的写法啊喂！
1 /************************************************************** 2 Problem: 3282 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:1732 ms 7 Memory:7840 kb 8 ****************************************************************/ 9 10 #include11 #include 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 }
（p.s. 不要问为什么窝改了代码风格。。。）