竹子听

50D： Treap's zag and zig

void zig(ll x)//左旋 

{

    if(root==t[x].fa)  root=x;//根节点

    ll ff=t[t[x].fa].fa;//存祖父节点

    t[t[x].fa].fa=x;把父亲节点的父亲改为当前节点

    if(ff!=0)//存在祖父节点

    {

        if(t[ff].lc==t[x].fa)//如果父亲节点是祖父节点的左儿子

        t[ff].lc=x;//把当前节点替换上去

        if(t[ff].rc==t[x].fa)//同理

        t[ff].rc=x;

    }

    if(t[x].lc!=0)//当前节点的左子树不为空

    t[t[x].lc].fa=t[x].fa;//移植过去

    t[t[x].fa].rc=t[x].lc;//移植

    t[x].lc=t[x].fa;//改箭头

    t[x].fa=ff;

    return;

}