我觉得还是有必要写一下有关splay模板解读

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入x数

删除x数(若有多个相同的数，因只删除一个)

查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)

查询排名为x的数

求x的前驱(前驱定义为小于x，且最大的数)

求x的后继(后继定义为大于x，且最小的数)

输入格式

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号( 1≤opt≤6 )

输出格式

对于操作3,4,5,6每行输出一个数，表示对应答案

#include
    
     #define re return#define inc(i,l,r) for(int i=l;i<=r;++i)const int maxn=100005;using namespace std;template
     
      inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}int tot,n,rt,ch[maxn][2],size[maxn],fa[maxn],cnt[maxn],val[maxn];inline bool chk(int x){re ch[fa[x]][1]==x;}inline void pushup(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];}inline void rotate(int x){    int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];    ch[z][chk(y)]=x;fa[x]=z;    ch[y][k]=w;fa[w]=y;    ch[x][k^1]=y;fa[y]=x;    pushup(y);pushup(x);}inline void splay(int x,int goal=0){    while(fa[x]!=goal)    {        int y=fa[x],z=fa[y];        if(z!=goal)        (chk(y)==chk(x))?rotate(y):rotate(x);        rotate(x);    }    if(!goal)    rt=x;}inline void insert(int x){    int u=rt,p=0;    此处p为0，防止p乱码    while(u&&val[u]!=x)    {        p=u;        u=ch[u][x>val[u]];    }    if(u)++cnt[u];    else    {        u=++tot;        if(p)ch[p][x>val[p]]=u;        fa[u]=p;        size[u]=cnt[u]=1;        val[u]=x;    }    splay(u,0);}inline int kth(int k){    int u=rt;    while(2333)    {        int y=ch[u][0];        if(cnt[u]+size[y]
      
       =k)u=y;        else re u;    }}inline void find(int x){    int u=rt;    while(ch[u][x>val[u]]&&val[u]!=x)    u=ch[u][x>val[u]];    splay(u,0);}inline int nt(int x,int f){    find(x);    if(!f&&x>val[rt])re rt;    if( f&&x
       
        1)--cnt[u],splay(u);    //！！！splay(u)=>pushup(u),因为cnt[u]也改变了    else ch[r][0]=0;    pushup(r);    pushup(rt);}inline void debug(){        inc(i,1,5)    printf("%d:ch[0]=%d ch[1]=%d\nsize=%d\n",i,ch[i][0],ch[i][1],size[i]);    }int main(){//  freopen("testdata.in","r",stdin);     freopen("in.txt","r",stdin);    int opt,x,u;    insert(147483647);    insert(-147483647);    rd(n);    inc(i,1,n)    {        rd(opt);rd(x);        switch(opt){            case 1:insert(x);break;            case 2:dete(x);break;            case 3:find(x);printf("%d\n",size[ch[rt][0]]);break;            case 4:printf("%d\n",val[kth(x+1)]);break;            case 5:printf("%d\n",val[nt(x,0)]);break;            case 6:printf("%d\n",val[nt(x,1)]);break;        }    }    re 0;}