treap

void insert(int &x,int y)//注意x前面的&。
{
     if (x==0)
     {
              x=++size;
              e[x].l=0;e[x].r=0;e[x].a=y;e[x].ll=0;e[x].rr=0;
              e[x].b=rand()*rand();
              return;
     }
     if (y>e[x].a)
     {
                  e[x].rr++;//如果大于X的话,则x的右儿子个数++；
                  insert(e[x].r,y);
                  if (e[x].b>e[e[x].r].b) right(x);
                  return;
     }
     if (y<=e[x].a)
     {
                   e[x].ll++;//同理,如果小于x的话,则X的左儿子个数++；
                   insert(e[x].l,y);
                   if (e[x].b>e[e[x].l].b) left(x);
                   return;
     }
}

由图上的旋转可知,旋转后x(要旋转的节点)的右节点(下面称J),J的左儿子变成了X的右儿子,因此E[X].RR=E[J].LL;

而J的左儿子,变成了X+X左儿子+J左儿子;

因此,只要如下面代码那样就可以实现了;

void right(int &x)
{
     int j=e[x].r;
     e[x].r=e[j].l;
     e[x].rr=e[j].ll;//
     e[j].l=x;
     e[j].ll=e[x].ll+e[j].ll+1;
     x=j;
}