TREAP 的基本操作

struct Node
{
    Node *ch[2]; //左右子树
    int r,v,s; //r 表示优先级 数值越大，优先级越高，v表示键值
    int cmp(int x)const
    {
        if(x==v) return -1;
        return x<v ? 0:1;
    }
    void maintain()
    {
        s=1;
        if(ch[0]!=NULL) s+=ch[0]->s;
        if(ch[1]!=NULL) s+=ch[1]->s;
    }
};
void Rotate(Node* &o,int d) //d = 0 代表左旋 d=1 代表右旋
{
    Node* k = o->ch[d^1];  //d=1 or d=0 -> d^1 = 1-d;
    o->ch[d^1] = k->ch[d];
    k->ch[d]=o;
    o->maintain();
    k->maintain();
    o=k;
}
void Insert(Node* &o, int x)
{
    if(o==NULL){ o = new Node(); o->ch[0] = o->ch[1] = NULL; o->v = x; o->r = rand();}
    else
    {
        int d=o->cmp(x);
        Insert(o->ch[d],x);
        if(o->ch[d]->r > o->r) Rotate(o,d^1);
    }
}
void Remove(Node* &o,int x)
{
    int d=o->cmp(x);
    if(d==-1)
    {
        if(o->ch[0]==NULL) o=o->ch[1];
        else if(o->ch[1]==NULL) o=o->ch[0];
        else
        {
            int d2 = (o->ch[0]->r > o->ch[1]->r ? 1:0);
            Rotate(o,d2);
            Remove(o->ch[d2],x);
        }
    }else
    Remove(o->ch[d],x);
}
int Find(Node* o,int x)
{
    while(o!=NULL)
    {
        int d = o->cmp(x);
        if(d==-1)return 1;
        else o=o->ch[d];
    }
    return 0;
}