非旋转式Treap FHQ_Treap

模板库 Treap

%%%%%%% Kirin %%%%%%%

[洛谷]普通平衡树

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n;
const int MAXN = 100000+9;
struct T{
    int val,RD,sz,ls,rs;
}tree[MAXN];
int root;
struct PAIR{
    int first,second;
    PAIR(){first=second=0;}
};
void update(int x){
    tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+1;
}
int New_Node(int x){//woooooooooooooooooooooooooooooo
    static int cnt=0;
    tree[++cnt].val=x;
    tree[cnt].sz=1;
    tree[cnt].RD=rand();
    return cnt;
}
PAIR split(int x,int val){
    PAIR re;
    if(x==0){
        return re;
    }
    if(val>=tree[x].val){
        re=split(tree[x].rs,val);
        tree[x].rs=re.first;
        re.first=x;
        update(x);
    }
    else{
        re=split(tree[x].ls,val);
        tree[x].ls=re.second;
        re.second=x;
        update(x);
    }
    return re;
}
int merge(int u,int v){
    if(u==0 || v==0){
        return u+v;
    }
    if(tree[u].RD<tree[v].RD){
        tree[u].rs=merge(tree[u].rs,v);
        update(u);
        return u;
    }
    else{
        tree[v].ls=merge(u,tree[v].ls);
        update(v);
        return v;
    }
}
void insert(int val){
    PAIR rt=split(root,val);
    root=merge(rt.first,merge(New_Node(val),rt.second));
}
void del(int val){
    PAIR lrt=split(root,val-1);
    PAIR rrt=split(lrt.second,val);
    rrt.first=merge(tree[rrt.first].ls,tree[rrt.first].rs);
    root=merge(lrt.first,merge(rrt.first,rrt.second));
}
int n2r(int val){
    PAIR rt=split(root,val-1);
    int re=tree[rt.first].sz+1;
    root=merge(rt.first,rt.second);
    return re;
}
int r2n(int x,int val){
    while(true){
        if(tree[tree[x].ls].sz>=val){
            x=tree[x].ls;
        }
        else if(tree[tree[x].ls].sz+1<val){
            val-=tree[tree[x].ls].sz+1;
            x=tree[x].rs;
        }
        else{
            return tree[x].val;
        }
    }
}
int pred(int val){
    PAIR rt=split(root,val-1);
    int re=r2n(rt.first,tree[rt.first].sz);
    root=merge(rt.first,rt.second);
    return re;
}
int succ(int val){
    PAIR rt=split(root,val);
    int re=r2n(rt.second,1);
    root=merge(rt.first,rt.second);
    return re;
}
int main(){
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)insert(x);
        if(opt==2)del(x);
        if(opt==3){printf("%d\n",n2r(x));}
        if(opt==4){printf("%d\n",r2n(root,x));}
        if(opt==5){printf("%d\n",pred(x));}
        if(opt==6){printf("%d\n",succ(x));}
    }
    return 0;
}