(int x)
| 73 | } |
| 74 | |
| 75 | public static void rotate(int x) { |
| 76 | int f = fa[x], g = fa[f]; |
| 77 | if (lr(x) == 0) { |
| 78 | ls[f] = rs[x]; |
| 79 | if (ls[f] != 0) { |
| 80 | fa[ls[f]] = f; |
| 81 | } |
| 82 | rs[x] = f; |
| 83 | } else { |
| 84 | rs[f] = ls[x]; |
| 85 | if (rs[f] != 0) { |
| 86 | fa[rs[f]] = f; |
| 87 | } |
| 88 | ls[x] = f; |
| 89 | } |
| 90 | if (!isroot(f)) { |
| 91 | if (lr(f) == 0) { |
| 92 | ls[g] = x; |
| 93 | } else { |
| 94 | rs[g] = x; |
| 95 | } |
| 96 | } |
| 97 | fa[f] = x; |
| 98 | fa[x] = g; |
| 99 | up(f); |
| 100 | up(x); |
| 101 | } |
| 102 | |
| 103 | public static void splay(int x) { |
| 104 | int siz = 0; |