splay旋转模板

void rotate(int x) {

    int y=f[x],z=son(x);f[x]=f[y];

    if (f[x]) t[f[x]][son(y)]=x;

    t[y][z]=t[x][1-z];

    if (t[x][1-z]) f[t[x][1-z]]=y;

    f[y]=x;t[x][1-z]=y;

}

void splay(int x,int y) {

    while (f[x]!=y) {

        if (f[f[x]]!=y)

            if (son(f[x])==son(x)) rotate(f[x]);

            else rotate(x);

        rotate(x);

    }

    if (!y) root=x;

}