FHQ Treap

在竞赛中我们一般使用FHQ Treap这种弱平衡的二叉搜索树。(又称无旋Treap)

它只有分裂与合并两种操作，相当好写。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
mt19937 rd(time(0));
struct node{
    int l,r,val,pri,size;
}t[N];
int cnt,root;
int newnode(int x){
    cnt++;
    t[cnt].l=t[cnt].r=0;
    t[cnt].size=1;
    t[cnt].val=x;
    t[cnt].pri=rd();
    return cnt;
}
void update(int u){
    t[u].size=t[t[u].l].size+t[t[u].r].size+1;
    return ;
}
void split(int u,int x,int &l,int &r){
    if(u==0){
        l=r=0;
        return ;
    }
    if(t[u].val<=x){
        l=u;
        split(t[u].r,x,t[u].r,r);
    }else {
        r=u;
        split(t[u].l,x,l,t[u].l);
    }
    update(u);
    return ;
}
int merge(int l,int r){
    if(!l||!r)return r+l;
    if(t[l].pri>t[r].pri){
        t[l].r=merge(t[l].r,r);
        update(l);
        return l;
    }else {
        t[r].l=merge(l,t[r].l);
        update(r);
        return r;
    }
}
void insert(int x){
    int l,r;
    split(root,x,l,r);
    root=merge(merge(l,newnode(x)),r);
    return ;
}
void del(int x){
    int l,r,p;
    split(root,x,l,r);
    split(l,x-1,l,p);
    p=merge(t[p].l,t[p].r);
    root=merge(merge(l,p),r);
    return ;
}
void xth(int x){
    int l,r;
    split(root,x-1,l,r);
    cout<<t[l].size+1<<'\n';
    root=merge(l,r);
    return ;
}
int kth(int u,int k){
    if(k==t[t[u].l].size+1)return u;
    if(k<=t[t[u].l].size)return kth(t[u].l,k);
    else return kth(t[u].r,k-t[t[u].l].size-1);
}
void preor(int x){
    int l,r;
    split(root,x-1,l,r);
    cout<<t[kth(l,t[l].size)].val<<'\n';
    root=merge(l,r);
    return ;
}
void sucor(int x){
    int l,r;
    split(root,x,l,r);
    cout<<t[kth(r,1)].val<<'\n';
    root=merge(l,r);
    return ;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        if(opt==1)insert(x);
        else if(opt==2)del(x);
        else if(opt==3)xth(x);
        else if(opt==4)cout<<t[kth(root,x)].val<<'\n';
        else if(opt==5)preor(x);
        else sucor(x);
    }
    return 0;
}