P3369

洛谷 Treap

Treap其实就是tree+heap
利用随机数给么个节点加上第二个值以实现更稳定的平衡

和Splay类似，都要旋转，不过这个是按堆的性质旋转，好写

#include<cstdio>
#include<cstdlib>
#define MAXN 1000009
using namespace std;
struct T{
    int ls,rs,rd,sz,num,val;
}tree[MAXN];
int root,size,ans;
int m;
void update(int x){
    tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;
}
void rotate_l(int &k){
    int y=tree[k].rs;
    tree[k].rs=tree[y].ls;
    tree[y].ls=k;
    tree[y].sz=tree[k].sz;
    update(k);
    k=y;
}
void rotate_r(int &k){
    int y=tree[k].ls;
    tree[k].ls=tree[y].rs;
    tree[y].rs=k;
    tree[y].sz=tree[k].sz;
    update(k);
    k=y;
}
void insert(int &k,int v){
    if(k==0){
        size++;k=size;tree[k].val=v;
        tree[k].sz=tree[k].num=1;tree[k].rd=rand();
        return;
    }
    tree[k].sz++;
    if(tree[k].val==v){
        tree[k].num++;
    }
    else if(v>tree[k].val){
        insert(tree[k].rs,v);
        if(tree[tree[k].rs].rd<tree[k].rd)rotate_l(k);
    }
    else{
        insert(tree[k].ls,v);
        if(tree[tree[k].ls].rd<tree[k].rd)rotate_r(k);
    }
}
void del(int &k,int v){
    if(k==0)return;
    if(tree[k].val==v){
        if(tree[k].num>1){
            tree[k].sz--;tree[k].num--;
            return;
        }
        if(tree[k].ls==0 || tree[k].rs==0)k=tree[k].ls+tree[k].rs;
        else if(tree[tree[k].ls].rd<tree[tree[k].rs].rd){
            rotate_r(k);
            del(k,v);
        }
        else{
            rotate_l(k);
            del(k,v);
        }
    }
    else if(tree[k].val<v){
        tree[k].sz--;
        del(tree[k].rs,v);
    }
    else{
        tree[k].sz--;
        del(tree[k].ls,v);
    }
}
int atrank(const int &k,int x){
    if(k==0)return 0;
    if(tree[k].val==x)
        return tree[tree[k].ls].sz+1;
    else if(tree[k].val<x)
        return tree[tree[k].ls].sz+tree[k].num+atrank(tree[k].rs,x);
    else
        return atrank(tree[k].ls,x);
}
int rerank(const int &k,int x){
    if(k==0) return 0;
    if(x<=tree[tree[k].ls].sz) return rerank(tree[k].ls,x);
    else if(x>tree[tree[k].ls].sz+tree[k].num)return rerank(tree[k].rs,x-tree[k].num-tree[tree[k].ls].sz);
    else return tree[k].val;
}
void pred(const int &k,int x){
    if(k==0)return;
    if(tree[k].val<x){
        ans=k;
        pred(tree[k].rs,x);
    }
    else{
        pred(tree[k].ls,x);
    }
}
void succ(const int &k,int x){
    if(k==0)return;
    if(tree[k].val>x){
        ans=k;
        succ(tree[k].ls,x);
    }
    else
        succ(tree[k].rs,x);
}
int main(){
    freopen("treap.in","r",stdin);
    scanf("%d",&m);
    while(m--){
        int opt,x;ans=0;
        scanf("%d%d",&opt,&x);
        if(opt==1) insert(root,x);
        if(opt==2) del(root,x);
        if(opt==3) printf("%d\n",atrank(root,x));
        if(opt==4) printf("%d\n",rerank(root,x));
        if(opt==5) {pred(root,x);printf("%d\n",tree[ans].val);}
        if(opt==6) {succ(root,x);printf("%d\n",tree[ans].val);}
    }
    return 0;
}

注释版

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct TREAP{
    int l,r,val,sz,recy,rd;
    //sz表示树的节点数，recy记录自己被重复了几次
    //rd表示该节点的优先级 
}t[1000000];
int m,size,root;
void update(int k){
    t[k].sz=t[t[k].l].sz+t[t[k].r].sz+t[k].recy;
    //更新维护 
}
void left_rotate(int &k){
    int y=t[k].r;t[k].r=t[y].l;t[y].l=k;
    t[y].sz=t[k].sz;update(k);k=y;
    //左旋，至于这里的k=y，由于下面的递归调用，
    //它会一直迭代，所以无需担心会有什么错误 
}
void right_rotate(int &k){
    int y=t[k].l;t[k].l=t[y].r;t[y].r=k;
    t[y].sz=t[k].sz;update(k);k=y;
    //右旋 
}
//以下函数的调用中(int k)表示在根为k的子树中
void insert(int &k,int x){//插入操作 
    if (k==0){//无节点时特判，
        //或是递归的边界，即插入叶节点 
        ++size;k=size;t[k].sz=t[k].recy=1;
        t[k].val=x;t[k].rd=rand();return ;
        //rand()生成随机的优先级，保证了期望复杂度 
    }
    ++t[k].sz;//每次向下找同时增加该节点1个节点数
    if (t[k].val==x) ++t[k].recy;
    //如果是相同数字，只需++recy即可 
    else if (x>t[k].val){
        insert(t[k].r,x);
        if (t[t[k].r].rd<t[k].rd) left_rotate(k);
        //插入后如果违反堆性质，就进行上浮 
    }else{
        insert(t[k].l,x);
        if (t[t[k].l].rd<t[k].rd) right_rotate(k);
    }
}
void del(int &k,int x){
    if (k==0) return ;//无节点就跳出 
    if (t[k].val==x){
        if (t[k].recy>1){
            --t[k].recy;--t[k].sz;return ;
            //如果重复了，只需--recy即可 
        }
        if (t[k].l*t[k].r==0) k=t[k].l+t[k].r;
        //如果左右儿子有为空的情况
        //或将其变为其儿子节点，或将其删除 
        else if (t[t[k].l].rd<t[t[k].r].rd) 
            right_rotate(k),del(k,x);
        //如果其左右儿子都有，选择优先级较大的，
        //保持以后的堆性质，同时将k节点下沉 
        else left_rotate(k),del(k,x);
    }
    else if (x>t[k].val)
        --t[k].sz,del(t[k].r,x);
    //如果关键值不同，继续向下找 
    else --t[k].sz,del(t[k].l,x);
}
int atrank(int k,int x){//寻找值为x的数的排名 
    if (k==0) return 0;
    if (t[k].val==x) return t[t[k].l].sz+1;
    //如果找的关键字，根据BST的性质，
    //则其排名为左子树的大小+1 
    else if (x>t[k].val)
        return t[t[k].l].sz+t[k].recy+atrank(t[k].r,x);
    //加上前面所有比它小的数，在右子树中找 
    else return atrank(t[k].l,x);
    //如果在左子树中找的话就不用加了 
}
int rerank(int k,int x){//寻找排名为x的数值 
    if (k==0) return 0;
    if (x<=t[t[k].l].sz) return rerank(t[k].l,x);
    //如果x小于了左子树的大小，那解一定在左子树中 
    else if (x>t[t[k].l].sz+t[k].recy)
        return rerank(t[k].r,x-t[k].recy-t[t[k].l].sz);
    //如果x大于的左子树的大小+k的重复次数，
    //那就在右子树中找 
    else return t[k].val;
    //否则就是找到解了(包含了重复数字中) 
}
void pred(int k,int x){//找前缀 
    if (k==0) return ;
    if (t[k].val<x){
        ans=k;pred(t[k].r,x);
        //找到了更优的解，就替换之
        //而且在其右子树中不可能再有更优的了
        //故向其左子树中找
    }else pred(t[k].l,x);
    //否则就往右子树中找 
}
void succ(int k,int x){//找后缀 
    if (k==0) return ;
    if (t[k].val>x){
        ans=k;succ(t[k].l,x);
    }else succ(t[k].r,x);
}
int main(){
    int f,x;
    scanf("%d",&m);
    for (int i=1;i<=m;++i){
        scanf("%d%d",&f,&x);ans=0;
        if (f==1) insert(root,x);
        if (f==2) del(root,x);
        if (f==3) printf("%d\n",atrank(root,x));
        if (f==4) printf("%d\n",rerank(root,x));
        if (f==5) {pred(root,x);printf("%d\n",t[ans].val);}
        if (f==6) {succ(root,x);printf("%d\n",t[ans].val);}
    }
    return 0;
}