splay旋转模板

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;
}