LCT 模板

  1 const int N = 1e5 + 5;
  2 
  3 int a[N];
  4 
  5 struct LCT {
  6     struct Tree {
  7         int son[2], tag, val, fa;
  8     } tr[N];
  9 
 10     void init(int ro) {
 11         tr[ro].son[0] = tr[ro].son[1] = tr[ro].fa = tr[ro].val = 0;
 12     }
 13 
 14     void modify(int ro) {
 15         swap(tr[ro].son[0], tr[ro].son[1]);
 16         tr[ro].tag ^= 1;
 17     }
 18 
 19     void pushdown(int ro) {
 20         if (tr[ro].tag) {
 21             modify(tr[ro].son[0]);
 22             modify(tr[ro].son[1]);
 23             tr[ro].tag = 0;
 24         }
 25     }
 26 
 27     void update(int ro) {
 28         tr[ro].val = tr[tr[ro].son[0]].val ^ tr[tr[ro].son[1]].val ^ a[ro];
 29     }
 30 
 31     int isroot(int ro) {
 32         int x = tr[ro].fa;
 33         if (!x) return 1;
 34         return (tr[x].son[0] != ro && tr[x].son[1] != ro);
 35     }
 36 
 37     void rotate(int ro) {
 38         int x = tr[ro].fa, y = tr[x].fa;
 39         int k = (tr[y].son[1] == x);
 40         if (tr[y].son[k] == x) {
 41             tr[y].son[k] = ro;
 42         }
 43         int z = (tr[x].son[1] == ro);
 44         tr[ro].fa = y;
 45         tr[x].fa = ro;
 46         tr[x].son[z] = tr[ro].son[z ^ 1];
 47         tr[tr[ro].son[z ^ 1]].fa = x;
 48         tr[ro].son[z ^ 1] = x;
 49         update(x), update(ro);
 50         if (tr[y].son[k] == ro) {
 51             update(y);
 52         }
 53     }
 54 
 55     void splay(int ro) {
 56         stack<int> st;
 57         st.push(ro);
 58         for (int i = ro; !isroot(i); i = tr[i].fa) st.push(tr[i].fa);
 59         while (!st.empty()) {
 60             pushdown(st.top());
 61             st.pop();
 62         }
 63         while (!isroot(ro)) {
 64             int x = tr[ro].fa;
 65             if (!isroot(x)) {
 66                 int y = tr[x].fa;
 67                 if ((tr[y].son[0] == x) ^ (tr[x].son[0] == ro)) rotate(ro);
 68                 else rotate(x);
 69             }
 70             rotate(ro);
 71         }
 72     }
 73 
 74     void access(int ro) {
 75         for (int i = 0; ro; i = ro, ro = tr[ro].fa) {
 76             splay(ro);
 77             tr[ro].son[1] = i;
 78             update(ro);
 79         }
 80     }
 81 
 82     void makeroot(int ro) {
 83         access(ro), splay(ro), modify(ro);
 84     }
 85 
 86     int getroot(int ro) {
 87         access(ro), splay(ro);
 88         int x = ro;
 89         while (tr[x].son[0]) x = tr[x].son[0];
 90         splay(x);
 91         return x;
 92     }
 93 
 94     void split(int x, int y) {
 95         makeroot(x), access(y), splay(y);
 96     }
 97 
 98     void link(int x, int y) {
 99         makeroot(x);
100         if (getroot(y) == x) return;
101         tr[x].fa = y;
102     }
103 
104     void cut(int x, int y) {
105         makeroot(x);
106         if (getroot(y) != x) return;
107         splay(y);
108         if (tr[x].son[1]) return;
109         tr[x].fa = 0;
110         tr[y].son[0] = 0;
111         update(y);
112     }
113 } Tr;