1 splay
1 void rotate(int o, int kind) { 2 int p = pre[o]; 3 ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p; 4 ch[pre[p]][ch[pre[p]][1] == p] = o, pre[o] = pre[p]; 5 ch[o][kind] = p, pre[p] = o; 6 } 7 void splay(int o, int goal) { 8 while (pre[o] != goal) { 9 if (pre[pre[o]] == goal) rotate(o, ch[pre[o]][0] == o); 10 else { 11 int p = pre[o], kind = ch[pre[p]][0] == p; 12 if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind); 13 else rotate(p, kind), rotate(o, kind); 14 } 15 } 16 if (goal == 0) root = o; 17 }
2 Treap
1 void rotate(int &o, int kind) { 2 int x = ch[o][!kind]; 3 ch[o][!kind] = ch[x][kind]; 4 ch[x][kind] = o; 5 o = x; 6 }
3 fhq_Treap
1 void split(int o, int keyy, int &x, int &y) { 2 if (!o) x = y = 0; 3 else { 4 if (key[o] <= keyy) x = o, split(ch[o][1], keyy, ch[o][1], y); 5 else y = o, split(ch[o][0], keyy, x, ch[o][0]); 6 } 7 } 8 int merge(int x, int y) { 9 if (!x || !y) return x+y; 10 if (lev[x] < lev[y]) { 11 ch[x][1] = merge(ch[x][1], y); 12 return x; 13 }else { 14 ch[y][0] = merge(x, ch[y][0]); 15 return y; 16 } 17 }
4 LCT
1 void rotate(int o, int kind) { 2 int p = pre[o]; 3 ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p; 4 if (isrt[p]) isrt[o] = 1, isrt[p] = 0; 5 else ch[pre[p]][ch[pre[p]][1] == p] = o; 6 pre[o] = pre[p]; 7 ch[o][kind] = p, pre[p] = o; 8 } 9 void splay(int o) { 10 push(o); 11 while (!isrt[o]) { 12 if (isrt[pre[o]]) rotate(o, ch[pre[o]][0] == o); 13 else { 14 int p = pre[o], kind = ch[pre[p]][0] == p; 15 if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind); 16 else rotate(p, kind), rotate(o, kind); 17 } 18 } 19 } 20 void access(int o) { 21 int y = 0; 22 while (o) { 23 splay(o); 24 isrt[ch[o][1]] = 1, isrt[ch[o][1] = y] = 0; 25 o = pre[y = o]; 26 } 27 } 28 void makeroot(int o) { 29 access(o), splay(o); 30 rev[o] ^= 1, swap(ch[o][0], ch[o][1]); 31 } 32 void link(int x, int y) { 33 makeroot(x); pre[x] = y; 34 } 35 void cut(int x, int y) { 36 makeroot(x), access(y), splay(y); 37 ch[y][0] = pre[x] = 0, isrt[x] = 1; 38 }
5 左偏树
1 int merge(int a, int b) { 2 if (!a || !b) return a+b; 3 if (key[a] > key[b]) swap(a, b); 4 ch[a][1] = merge(ch[a][1], b); 5 if (dist[ch[a][0]] < dist[ch[a][1]]) swap(ch[a][0], ch[a][1]); 6 dist[a] = dist[ch[a][1]]+1; 7 return a; 8 }
