中山day10

今天没比赛，自学，发现平衡树没打过，打了一下。
平衡树有很多种，代码量和性能都不尽相同，我选择了相对好打的无旋Treap（FHQ Treap）（因为我懒）
板子

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,val[100010],key[100010],ls[100010],rs[100010],tot=1,root=0,siz[100010];
void undate_siz(int p){
    siz[p]=1;
    if(ls[p]!=0)siz[p]+=siz[ls[p]];
    if(rs[p]!=0)siz[p]+=siz[rs[p]];
}
int new_node(int x){
    val[tot]=x;
    key[tot]=rand();
    ls[tot]=0;
    rs[tot]=0;
    siz[tot]=1;
    return tot++;
}
void split(int p,int k,int& l,int& r){
    if(p==0){
        l=0;
        r=0;
        return;
    }
    if(val[p]<=k){
        split(rs[p],k,l,r);
        rs[p]=l;
        l=p;
    }
    if(val[p]>k){
        split(ls[p],k,l,r);
        ls[p]=r;
        r=p;
    }
    undate_siz(p);
}
void split_rank(int p,int k,int& l,int& r){
    if(p==0){
        l=0;
        r=0;
        return;
    }
    if(siz[ls[p]]<k){
        split_rank(rs[p],k-siz[ls[p]]-1,l,r);
        rs[p]=l;
        l=p;
    }
    if(siz[ls[p]]>=k){
        split_rank(ls[p],k,l,r);
        ls[p]=r;
        r=p;
    }
    undate_siz(p);
}
int merge(int l,int r){
    if(l==0)return r;
    if(r==0)return l;
    if(key[l]<=key[r]){
        ls[r]=merge(l,ls[r]);
        undate_siz(r);
        return r;
    }
    if(key[l]>key[r]){
        rs[l]=merge(rs[l],r);
        undate_siz(l);
        return l;
    }
}
void insert(int x){
    int l,r;
    split(root,x,l,r);
    int p=new_node(x);
    root=merge(l,p);
    root=merge(root,r);
}
void erase(int x){
    int l,r,tmp;
    split(root,x,l,r);
    split(l,x-1,l,tmp);
    int er;
    split_rank(tmp,1,er,tmp);
    root=merge(l,tmp);
    root=merge(root,r);
}
int find_rank(int x){
    int l,r;
    split(root,x-1,l,r);
    int ret=siz[l]+1;
    root=merge(l,r);
    return ret;
}
int find_val(int x){
    int l,r,tmp;
    split_rank(root,x,l,r);
    split_rank(l,x-1,l,tmp);
    int ret=val[tmp];
    root=merge(l,tmp);
    root=merge(root,r);
    return ret;
}
int find_pre(int x){
    int l,r,tmp;
    split(root,x-1,l,r);
    split_rank(l,siz[l]-1,l,tmp);
    int ret=val[tmp];
    root=merge(l,tmp);
    root=merge(root,r);
    return ret;
}
int find_suf(int x){
    int l,r,tmp;
    split(root,x,l,r);
    split_rank(r,1,tmp,r);
    int ret=val[tmp];
    root=merge(l,tmp);
    root=merge(root,r);
    return ret;
}
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int o,x;
        cin>>o>>x;
        if(o==1){
            insert(x);
        }
        if(o==2){
            erase(x);
        }
        if(o==3){
            cout<<find_rank(x)<<endl;
        }
        if(o==4){
            cout<<find_val(x)<<endl;
        }
        if(o==5){
            cout<<find_pre(x)<<endl;
        }
        if(o==6){
            cout<<find_suf(x)<<endl;
        }
    }
    return 0;
}

其实查询可以用简单的递归实现，但为了减少代码量，我通过纯分裂合并实现了这个操作，使得常数变得有亿点大（能过就行）