rt

用的treap

#include<bits/stdc++.h>
#define inf 2147283647
using namespace std;
const int maxn=3e6;
struct node
{
    int l,r;
    int k,t;
    int cnt,siz;
}a [maxn];
int rt,n,tot;
void ne(int k)
{
    a[++tot].k=k;
    a[tot].t=rand();
     a[tot].siz=a[tot].cnt=1;
}
void update(int k)
{
    a[k].siz=a[a[k].l].siz+a[a[k].r].siz+a[k].cnt;
}
void build()
{
    ne(-inf);
    ne(inf);
    rt=1;
    update(rt);
}
void zig(int &k)
{
    int x=a[k].l;
    a[k].l=a[x].r;
    a[x].r=k;
    k=x;
    update(a[k].r);
    update(k);
}
void zag(int &k)
{
    int x=a[k].r;
    a[k].r=a[x].l;
    a[x].l=k;
    k=x;
    update(a[k].l);
    update(k);
}
void ins(int &p,int k)
{
    if(p==0)
    {
        ne(k);
        p=tot;
        return;
    }
    if(a[p].k==k)
    {
        ++a[p].cnt;
        update(p);
        return;
    }
    if(a[p].k<k)
    {
        ins(a[p].r,k);
        if(a[p].t<a[a[p].r].t)
            zag(p);
    }
    
    // if(a[p].k<k)
    else
    {
        ins(a[p].l,k);
        if(a[p].t>a[a[p].r].t)
            zig(p);
    }
    update(p);
}
void remove(int &p,int k)
{
    if(p==0)
        return;
    if(a[p].k==k)
    {
        if(a[p].cnt>1)
        {
            --a[p].cnt;
            update(p);
            return;
        }
        if(a[p].l||a[p].r)
        {
            if(a[p].r==0||a[a[p].l].t>a[a[p].r].t)
            {
                zig(p);
                remove(a[p].r,k);
                
            }
            else
            {
                zag(p);
                remove(a[p].l,k);
            }
            update(p);
        }
            else
            
                p=0;
                return;
            
        
    }    
    if(k<a[p].k)
    {
        remove(a[p].l,k);
        
    }
    else
        remove(a[p].r,k);
        update(p);
}
int getpre(int k)
{
    int s=1;
    int p=rt;
    while(p)
    {
        if(a[p].k==k)
        {
            p=a[p].l;
            while(a[p].r!=0)
            {
                p=a[p].r;
            }
            return a[p].k;

        }
        if(a[p].k<k&&a[p].k>a[s].k)
            s=p;
        if(a[p].k>k)
            p=a[p].l;
        else
            p=a[p].r;
    }
    return a[s].k;
}
int getnxt(int k)
{
    int s=2;
    int p=rt;
    while(p)
    {
        if(a[p].k==k)
        {
            p=a[p].r;
            while(a[p].l!=0)
            {
                p=a[p].l;
            }
            return a[p].k;

        }
        if(a[p].k>k&&a[p].k<a[s].k)
            s=p;
        if(a[p].k>k)
            p=a[p].l;
        else
            p=a[p].r;
    }
    return a[s].k;

}
int getrank(int p,int k)
{
    if(p==0)
        return 0;
    if(a[p].k==k)
    {
        return a[k].siz+1;
    }
    if(a[p].k<k)
    {
        getrank(a[p].r,k);
    }
    else
        getrank(a[p].l,k);

 }
int getval(int p,int rank)
{
    if(p==0)
        return inf;
    if(a[a[p].l].siz>=rank)
    {
        return getval(a[p].l,rank);
    }
    else if(a[a[p].l].siz+a[p].cnt>=rank)
        return a[p].k;
    else
        return getval(a[p].r,rank-a[p].cnt-a[a[p].l].siz);
}
int main(){
    cin>>n;
    build();
    for(int i=1;i<=n;i++)
    {
        int op,x;
        cin>>op>>x;
        switch(op)
        {
            case 1:ins(rt,x);break;
            case 2:remove(rt,x);break;
            case 3:cout<<getrank(rt,x)-1<<endl;break;
            case 4:cout<<getval(rt,x+1)<<endl;break;
            case 5:cout<<getpre(x)<<endl;break;
            case 6:cout<<getnxt(x)<<endl;break;
        }
    }
    return 0;
}