关键部分代码：

void rotate(int x){    if(x == rt)    return ;    int p = f[x], y = (x == r(p)), z = (p == r(f[p]));    c[z][f[p]] = x, f[x] = f[p];    c[y][p] = c[!y][x], f[c[!y][x]] = p;    c[!y][x] = p, f[p] = x;    update(p);    update(x);    if(rt == p)    rt = x;}void splay(int x){    for(int a[2] = {f[x], x}; f[x] && f[f[x]]; rotate(x), a[0] = f[x])        rotate(a[(r(f[x]) == x) ^ (r(f[f[x]]) == f[x])]);    if(f[x])    rotate(x);    }