Splay模板

 1 #define mx 100010
 2 int f[mx], c[mx][2], s[mx];
 3 inline void up (int x)
 4 {
 5     s[x] = s[c[x][0]] + s[c[x][1]] + 1;
 6 }
 7 inline int rotate (int i)
 8 {
 9     int fa = f[i], d = c[fa][1] == i;
10     f[i] = f[fa], fa > 0 ? c[f[fa]][c[f[fa]][1] == fa] = i : 0;
11     (c[fa][d] = c[i][!d]) ? f[c[i][!d]] = fa : 0;
12     up (c[f[fa] = i][!d] = fa);
13     return i;
14 }
15 inline void splay (int i)
16 {
17     for (int fa = f[i]; fa; fa = f[rotate (i)])
18         f[fa] ? rotate (c[fa][1] == i ^ c[f[fa]][1] == fa ? i : fa): 0;
19     up (i);
20 }