[模板]普通平衡树-无旋Treap(FHQ Treap)

//非旋Treap(FHQ Treap)
#include
#include
#include<string>
#include
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct FHQ_Treap{
    int ch[2],val,rnk,sze;
    FHQ_Treap(){ch[0]=ch[1]=val=rnk=sze=0;}
}tree[WR];
int n,root,tot;
int x,y,z;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;//?????没加*w?????
}
void pushup(int k){//这里貌似不需要记录副本数了
    tree[k].sze=tree[tree[k].ch[0]].sze+tree[tree[k].ch[1]].sze+1;
}
int add_point(int v){
    tree[++tot].sze=1;
    tree[tot].val=v;
    tree[tot].rnk=rand();//但别的还是差不多的
    return tot;
}
int treap_merge(int x,int y){//平衡树合并
    if(!x||!y) return x+y;//酷似线段树合并
    if(tree[x].rnk//如果x号节点比y号节点排名小
        tree[x].ch[1]=treap_merge(tree[x].ch[1],y);//把y合并到x的右子树上
        pushup(x);
        return x;
    }else{
        tree[y].ch[0]=treap_merge(x,tree[y].ch[0]);//否则把x合并到y的左子树上
        pushup(y);
        return y;
    }
}
void treap_split(int pos,int v,int &x,int &y){
    if(!pos) x=y=0;//分裂操作，把值小于v的和大于v的劈开
    else{
        if(tree[pos].val<=v){
            //假如一个点的权值小于k
            //那么它的所有左子树都要分到左边的树里，然后遍历它的右儿子。
            x=pos;
            treap_split(tree[pos].ch[1],v,tree[pos].ch[1],y);
        }else{
            //假如一个点的权值大于k
            //那么它的所有右子树都要分到右边的树里，然后遍历它的左儿子。
            y=pos;
            treap_split(tree[pos].ch[0],v,x,tree[pos].ch[0]);
        }
        pushup(pos);
    }
}
int get_num(int id,int v){//这里返回的是树的节点编号，不是节点值
    while(1==1){
        if(v<=tree[tree[id].ch[0]].sze){//如果比当前排名小去左子树找
            id=tree[id].ch[0];
        }else if(v==tree[tree[id].ch[0]].sze+1){//如果就是当前节点返回
            return id;
        }else{
            v-=tree[tree[id].ch[0]].sze+1;//否则去右子树找
            id=tree[id].ch[1];
        }
    }
}
int main(){
    n=read();root=0;
    for(int i=1;i<=n;i++){
        int opt=read(),v=read();
        if(opt==1){//insert
            //插入一个权值为v的点，把树按照v的权值split成两个，再按照顺序merge回去
            treap_split(root,v,x,y);
            root=treap_merge(treap_merge(x,add_point(v)),y);
        }
        if(opt==2){//delete
            //删除权值为v的点，把树按照v分成两个a,b,
            //再把a按照v-1分成c,d。
            //把c的两个子儿子merge起来，再merge(merge(c,d),b)
            treap_split(root,v,x,z);
            treap_split(x,v-1,x,y);
            y=treap_merge(tree[y].ch[0],tree[y].ch[1]);
            root=treap_merge(treap_merge(x,y),z);
        }
        if(opt==3){//get_rank
            //把root按v-1 split成x,y，排名是x的siz
            treap_split(root,v-1,x,y);
            printf("%d\n",tree[x].sze+1);
            root=treap_merge(x,y);
        }
        if(opt==4){
            printf("%d\n",tree[get_num(root,v)].val);
        }
        if(opt==5){
            //找前驱的话把root按v-1 split成x,y，在x里面找最大值
            treap_split(root,v-1,x,y);
            printf("%d\n",tree[get_num(x,tree[x].sze)].val);
            root=treap_merge(x,y);
        }
        if(opt==6){
            //找后继的话把root按v split成x,y，在y里找最小值
            treap_split(root,v,x,y);
            printf("%d\n",tree[get_num(y,1)].val);
            root=treap_merge(x,y);
        }
    }
    return 0;
}