普通平衡树 fhq yyds

#include<bits/stdc++.h>
using namespace std;
int cnt;
int root;
int x,y,z;
struct node{
   
    int l;
    int r;
    int val;
    int key;
    int sz;
}fhq[100010];
int newnode(int x)
{
   
    ++cnt;
    fhq[cnt].sz=1;
    fhq[cnt].key=rand();
    fhq[cnt].val=x;
    return cnt;
}
void update(int x)
{
   
    fhq[x].sz=fhq[fhq[x].l].sz+fhq[fhq[x].r].sz+1;
}
void split(int now,int val,int &x,int &y)
{
   
    if(!now)
    {
   
        x=y=0;
        return ;
    }
    if(fhq[now].val<=val)
    {
   
        x=now;
        split(fhq[now].r,val,fhq[now].r,y);
     // update(x);
    }
    else
    {
   
        y=now;
        split(fhq[now].l,val,x,fhq[now].l);
      // update(y);
    }
    update(now);
}
int merge(int x,int y)
{
   
    if(!x || !y)
    return x+y;
    if(fhq[x].key<fhq[y].key)
    {
   
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
    else
    {
   
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }
}
void insert(int val){
   
    split(root,val,x,y);
    root=merge(merge(x,newnode(val)),y);
}
void del(int val){
   
    split(root,val,x,y);
    split(x,val-1,x,z);
    z=merge(fhq[z].l,fhq[z].r);
    root=merge(merge(x,z),y);
}
int getrank(int val)
{
   
    split(root,val-1,x,y);
    int res=fhq[x].sz+1;
    root=merge(x,y);
    return res;
}
int kth(int k)
{
   
    int now=root;
    while(now)
    {
   
        if(fhq[fhq[now].l].sz+1==k)
        break;
        else if(fhq[fhq[now].l].sz>=k)
        now=fhq[now].l;
        else
        k-=fhq[fhq[now].l].sz+1,now=fhq[now].r;
    }
    return fhq[now].val;
}
int pre(int val)
{
   
    split(root,val-1,x,y);
    int now=x;
    while(fhq[now].r)
    now=fhq[now].r;
    int res=fhq[now].val;
    root = merge(x,y);
    return res;
}
int nxt(int val)
{
   
    split(root,val,x,y);
    int now=y;
    while(fhq[now].l)
    now=fhq[now].l;
    int res=fhq[now].val;
    root=merge(x,y);
    return res;
}
int main()
{
   
    srand(time(NULL));
    int t;
    cin>>t;
    while(t--)
    {
   
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
   
            insert(x);
        }
        else if(op==2)
        {
   
            del(x);
        }
        else if(op==3)
        {
   
            cout<<getrank(x)<<endl;
        }
        else if(op==4)
        {
   
            cout<<kth(x)<<endl;
        }
        else if(op==5)
        {
   
            cout<<pre(x)<<endl;
        }
        else
        {
   
            cout<<nxt(x)<<endl;
        }
    }
    return 0;
}