记录编号	600120	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	djyqjy	是否通过	通过
代码语言	C++	运行时间	0.435 s
提交时间	2025-04-15 22:17:10	内存使用	5.80 MiB

#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=100010,INF=0x3f3f3f3f;
int n;
struct Splay
{
   int rt,jsq;
   int fa[N],s[N][2],val[N],cnt[N],sz[N];
   Splay()
   {
        rt=jsq=0;
        memset(fa,0,sizeof(fa));memset(s,0,sizeof(s));memset(val,0,sizeof(val));
        memset(cnt,0,sizeof(cnt));memset(sz,0,sizeof(sz));
    }
    int son(int x){return s[fa[x]][1]==x;}
    void push_up(int x){sz[x]=sz[s[x][0]]+sz[s[x][1]]+cnt[x];}
    void rotate(int x)
    {
        int y=fa[x],z=fa[y],ls=son(x);
        s[y][ls]=s[x][!ls];if(s[x][!ls]) fa[s[x][!ls]]=y;
        if(z) s[z][son(y)]=x;fa[x]=z;
        fa[y]=x;s[x][!ls]=y;
        push_up(y);push_up(x);
        return;
    }
    void splay(int &z,int x)
    {
        int ls=fa[z],f=fa[x];
        while(fa[x]!=ls)
        {
            if(fa[f]!=ls) rotate(son(x)==son(f)?f:x);
            rotate(x);f=fa[x];
        }
        z=x;
        return;
    }
    void find(int &z,int v)
    {
        int x=z,f=fa[z];
        while(x&&val[x]!=v) f=x,x=s[x][v>val[x]];
        splay(z,x?x:f);
    }
    int get_val(int &z,int rk)
    {
        int x=z;
        while(1)
        {
            if(sz[s[x][0]]>=rk) x=s[x][0];
            else if(sz[s[x][0]]+cnt[x]>=rk) break;
            else rk-=sz[s[x][0]]+cnt[x],x=s[x][1];
        }
        splay(z,x);
        return val[x];
    }
    int merge(int x,int y)
    {
        if(!x||!y) return x|y;
        get_val(y,1);
        s[y][0]=x;fa[x]=y;
        push_up(y);
        return y;
    }
    void insert(int v)
    {
        int x=rt,f=0;
        while(x&&val[x]!=v) f=x,x=s[x][v>val[x]];
        if(x)
        {
            cnt[x]++;
            sz[x]++;
            splay(rt,x);
            return;
        }
        x=++jsq;
        val[x]=v;
        cnt[x]=sz[x]=1;
        fa[x]=f;
        if(f) s[f][v>val[f]]=x;
        splay(rt,x);
        return;
    }
    bool remove(int v)
    {
        find(rt,v);
        if(!rt||val[rt]!=v) return 0;
        cnt[rt]--;sz[rt]--;
        if(!cnt[rt])
        {
            int x=s[rt][0],y=s[rt][1];
            fa[x]=fa[y]=s[rt][0]=s[rt][1]=0;
            rt=merge(x,y);
        }
        return 1;
    }
    int get_pre(int v)
    {
        find(rt,v);
        if(rt&&val[rt]<v) return val[rt];
        int x=s[rt][0];
        if(!x) return -INF;
        while(s[x][1]) x=s[x][1];
        splay(rt,x);
        return val[rt];
    }
    int get_next(int v)
    {
        find(rt,v);
        if(rt&&val[rt]>v) return val[rt];
        int x=s[rt][1];
        if(!x) return INF;
        while(s[x][0]) x=s[x][0];
        splay(rt,x);
        return val[rt];
    }
    int get_rank(int v)
    {
        find(rt,v);
        return sz[s[rt][0]]+(val[rt]<v?cnt[rt]:0)+1;
    }
}a;
int main()
{
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
    n=re();
    for(int i=1,op;i<=n;i++)
    {
        op=re();
        if(op==1) a.insert(re());
        else if(op==2) a.remove(re());
        else if(op==3) printf("%d\n",a.get_rank(re()));
        else if(op==4) printf("%d\n",a.get_val(a.rt,re()));
        else if(op==5) printf("%d\n",a.get_pre(re()));
        else printf("%d\n",a.get_next(re()));
    }
    return 0;
}