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 }