Splay基本操作。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=1e5+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int d,f,son[2],c,n;}t[N];int len,root;
void add(int d,int f){t[++len]=(node){d,f,{0,0},1,1};t[f].son[t[f].d<d]=len;}
void update(int p){t[p].c=t[p].n+t[t[p].son[0]].c+t[t[p].son[1]].c;}
void rotate(int p,int w)
{
    int f=t[p].f,gf=t[f].f;
    int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
    r=p;R=gf;t[R].son[t[R].son[1]==f]=r;t[r].f=R;
    r=f;R=p;t[R].son[w]=r;t[r].f=R;update(f),update(p);
}
void splay(int p,int rt)
{
    while(t[p].f!=rt)
    {
        int f=t[p].f,gf=t[f].f;
        if(gf==rt)rotate(p,t[f].son[0]==p);
        else
        {
            if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
            else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
            else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
            else rotate(f,0),rotate(p,0);
             
        }
    }
    if(!rt)root=p;
}
int get_id(int d)
{
    int p=root;
    while(t[p].d!=d)
    {
        if(t[p].d<d)
        {
            if(!t[p].son[1])break;
            p=t[p].son[1];
        }
        else
        {
            if(!t[p].son[0])break;
            p=t[p].son[0];
        }
    }
    return p;
}
void ins(int d)
{
    if(!root){add(d,0);root=1;return ;}
    int p=get_id(d);
    if(t[p].d==d)++t[p].n,update(p),splay(p,0);
    else add(d,p),update(p),splay(len,0);
}
void del(int d)
{
    int p=get_id(d);splay(p,0);
    if(t[p].n>1){--t[p].n,update(p);return ;}
    if(!t[p].son[0]&&!t[p].son[1])root=0,len=0;
    else if(t[p].son[0]&&!t[p].son[1])root=t[p].son[0],t[root].f=0;
    else if(!t[p].son[0]&&t[p].son[1])root=t[p].son[1],t[root].f=0;
    else
    {
        int R=t[p].son[0];while(t[R].son[1])R=t[R].son[1];splay(R,p);
        int r=t[p].son[1];t[r].f=R;t[R].son[1]=r;root=R;t[root].f=0;
        splay(R,0);
    }
}
int rk(int d)
{
    int p=get_id(d);splay(p,0);
    return t[t[p].son[0]].c+1;
}
int kth(int k)
{
    int p=root;
    while(233)
    {
        int lc=t[p].son[0],rc=t[p].son[1];
        if(t[lc].c>=k)p=lc;
        else if(t[lc].c+t[p].n<k)k-=t[lc].c+t[p].n,p=rc;
        else break;
    }
    return p;
}
int prv(int d)
{
    int p=get_id(d);splay(p,0);
    if(d<=t[p].d&&t[p].son[0])
        for(p=t[p].son[0];t[p].son[1];p=t[p].son[1]);
    //if(d<t[p].d)return -1;没有更小的数 
    return p;
}
int nxt(int d)
{
    int p=get_id(d);splay(p,0);
    if(d>=t[p].d&&t[p].son[1])
        for(p=t[p].son[1];t[p].son[0];p=t[p].son[0]);
    return p;
}
int main()
{
    int n;qr(n);len=0;root=0;
    for(int i=1;i<=n;i++)
    {
        int opt,x;qr(opt),qr(x);
        if(opt==1)ins(x);
        else if(opt==2)del(x);
        else if(opt==3)qw(rk(x)),puts("");
        else if(opt==4)qw(t[kth(x)].d),puts("");
        else if(opt==5)qw(t[prv(x)].d),puts("");
        else qw(t[nxt(x)].d),puts("");
    }
    return 0;
}