FHQ Treap

今天来介绍一个神奇的平衡树 fhq treap 啦

之所以叫 fhq，是因为是2003年国家集训队范浩强神仙发明的啦

模板

#include<iostream>
#define N 1000005
#define ls(x) (tr[x].l)
#define rs(x) (tr[x].r)
#define val(x) (tr[x].val)
#define siz(x) (tr[x].siz)
int tot;
struct{
    int l,r,val,key,cnt,siz;
}tr [N];
using namespace std;
void update(int u){
    siz(u)=siz(ls(u))+siz(rs(u))+tr[u].cnt;
}
void split(int u,int &x,int &y,int key){
    if(!u){
        x=y=0;
        return;
    }
    if(val(u)<=key){
        x=u,split(rs(u),rs(u),y,key);
    }else{
        y=u,split(ls(u),x,ls(u),key);
    }
    update(u);
}
int merge(int x,int y){
    if(!x||!y) return x|y;
    if(tr[x].key<tr[y].key){
        rs(x)=merge(rs(x),y);
        update(x);
        return x;
    }else{
        ls(y)=merge(x,ls(y));
        update(y);
        return y;
    }
}
int kth(int x,int k){
    if(!x) throw "invalid";
    if(siz(ls(x))>=k) return kth(ls(x),k);
    else if(siz(ls(x))+tr[x].cnt>=k) return val(x);
    else return kth(rs(x),k-siz(ls(x))-tr[x].cnt);
}
int rt=0;
int main(){
    int n,opt,x,lx,ly,px,py;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>opt>>x;
        if(opt==1){
            split(rt,lx,ly,x);
            split(lx,px,py,x-1);
            if(py) tr[py].cnt++,tr[py].siz++;
            else tr[py=++tot]={0,0,x,rand(),1,1};
            lx=merge(px,py),rt=merge(lx,ly);
        }
        if(opt==2){
            split(rt,lx,ly,x);
            split(lx,px,py,x-1);
            if(--tr[py].cnt,--tr[py].siz) lx=merge(px,py);
            else lx=px;
            rt=merge(lx,ly);
        }
        if(opt==3){
            split(rt,lx,ly,x);
            split(lx,px,py,x-1);
            cout<<siz(px)+1<<"\n";
            lx=merge(px,py),rt=merge(lx,ly);
        }
        if(opt==4){
            cout<<kth(rt,x)<<"\n";
        }
        if(opt==5){
            split(rt,lx,ly,x-1);
            cout<<kth(lx,siz(lx))<<"\n";
            rt=merge(lx,ly);
        }
        if(opt==6){
            split(rt,lx,ly,x);
            cout<<kth(ly,1)<<"\n";
            rt=merge(lx,ly);
        }
    }
}