一道码力题，调了我一天。

把最小的元素$x$旋到根，深度改变的只有$x$变为$1$，以及除$x$子树的所有点深度$+1$

最大元素一样的。

删掉最小元素$x$，深度改变的只有$x$子树(深度$-1$)。

插入的话，因为二叉搜索树的连续性，要么将$x$插入在它的前驱，要么后继，取决于哪个深度大。

细节的话，注意父亲结点是否存在，子树是否存在。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=1e9+7,N=1e5+10;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    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;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct Splay
{
    struct node{int f,son[2],d;}t[N];int len,root;
    void add(int d,int f){t[++len]=(node){f,{0,0},d};t[f].son[d>t[f].d]=len;}
    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;
    }
    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(d<t[p].d)
            {
                if(!t[p].son[0])break;
                p=t[p].son[0];
            }
            if(d>t[p].d)
            {
                if(!t[p].son[1])break;
                p=t[p].son[1];
            }
        }
        return p;
    }
    void ins(int d)
    {
        if(!root){add(d,0);root=len;return ;}
        int p=get_id(d);add(d,p);splay(len,0);
    }
    void del(int d)
    {
        int p=get_id(d);splay(p,0);
        if(!t[p].son[0]&&!t[p].son[1])root=0,len=0;
        else if(t[p].son[1]&&!t[p].son[0])t[root=t[p].son[1]].f=0;
        else if(t[p].son[0]&&!t[p].son[1])t[root=t[p].son[0]].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].son[1]=r;t[r].f=R;t[root=R].f=0;splay(R,0);
        }
    }
    int nxt(int d)
    {
        int p=get_id(d);splay(p,0);
        if(t[p].d<=d&&t[p].son[1])
            for(p=t[p].son[1];t[p].son[0];p=t[p].son[0]);
        if(t[p].d<=d)return 0;
        return t[p].d;
    }
    int prv(int d)
    {
        int p=get_id(d);splay(p,0);
        if(t[p].d>=d&&t[p].son[0])
            for(p=t[p].son[0];t[p].son[1];p=t[p].son[1]);
        if(t[p].d>=d)return 0;
        return t[p].d;
    }
    int fl(){int p=root;while(t[p].son[0])p=t[p].son[0];return t[p].d;}
    int fr(){int p=root;while(t[p].son[1])p=t[p].son[1];return t[p].d;}
}spl;
int n;
struct SGT
{
    int c[N];
    SGT(){memset(c,0,sizeof(c));}
    inline void add(int x,int d){for(;x<=n;x+=x&-x)c[x]+=d;}
    inline void change(int l,int r,int d){add(l,d);add(r+1,-d);}
    inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
    inline void modify(int x,int d)
    {
        int w=ask(x);d=d-w;
        add(x,d),add(x+1,-d);
    }
    /*struct node{int w,ad;}t[N<<2];
    void pushdown(int p)
    {
        if(t[p].ad)
            t[p<<1].ad+=t[p].ad,t[p<<1|1].ad+=t[p].ad,
            t[p<<1].w+=t[p].ad,t[p<<1|1].w+=t[p].ad,t[p].ad=0;
    }
    void modify(int p,int l,int r,int x,int d)
    {
        if(l==r){t[p].w=d;return ;}
        pushdown(p);int mid=l+r>>1;
        if(x<=mid)modify(p<<1,l,mid,x,d);
        else modify(p<<1|1,mid+1,r,x,d);
    }
    void change(int p,int l,int r,int x,int ad)
    {
        if(l==r){t[p].w+=ad;return ;}
        pushdown(p);int mid=l+r>>1;
        if(x<=mid)change(p<<1,l,mid,x,ad);
        else change(p<<1|1,mid+1,r,x,ad);
    }
    void change(int p,int l,int r,int L,int R,int ad)
    {
        if(L<=l&&R>=r){t[p].ad+=ad,t[p].w+=ad;return ;}
        pushdown(p);int mid=l+r>>1;
        if(L<=mid)change(p<<1,l,mid,L,R,ad);
        if(R>mid)change(p<<1|1,mid+1,r,L,R,ad);
    }
    int query(int p,int l,int r,int x)
    {
        if(l==r)return t[p].w;
        pushdown(p);int mid=l+r>>1;
        if(x<=mid)return query(p<<1,l,mid,x);
        return query(p<<1|1,mid+1,r,x);
    }*/
}sgt;
struct node{int f,son[2];}t[N];int root,len,cnt;
void ins(int p)
{
    ++len;spl.ins(p);
    if(!root){root=p;t[root].f=0;sgt.modify(p,1);puts("1");return ;}
    int nxt=spl.nxt(p),prv=spl.prv(p),w1=0,w2=0;
    if(nxt)w1=sgt.ask(nxt);
    if(prv)w2=sgt.ask(prv);
    if(w1>w2)t[nxt].son[0]=p,t[p].f=nxt,sgt.modify(p,w1+1);
    else t[prv].son[1]=p,t[p].f=prv,sgt.modify(p,w2+1);
    qw(max(w1+1,w2+1));puts("");
}
void romin()
{
    int p=spl.fl();
    //while(t[p].son[0])p=t[p].son[0];
    qw(sgt.ask(p));puts("");
    if(p==root)return ;
    sgt.change(1,n,1);
    if(p+1<=t[p].f-1)sgt.change(p+1,t[p].f-1,-1);
    sgt.modify(p,1);
    t[t[p].f].son[0]=t[p].son[1];if(t[p].son[1])t[t[p].son[1]].f=t[p].f;
    t[p].son[1]=root;t[root].f=p;root=p;t[p].f=0;
}
void romax()
{
    int p=spl.fr();
    //while(t[p].son[1])p=t[p].son[1];
    qw(sgt.ask(p));puts("");
    if(p==root)return ;
    sgt.change(1,n,1);
    if(t[p].f+1<=p-1)sgt.change(t[p].f+1,p-1,-1);
    sgt.modify(p,1);
    t[t[p].f].son[1]=t[p].son[0];if(t[p].son[0])t[t[p].son[0]].f=t[p].f;
    t[p].son[0]=root;t[root].f=p;root=p;t[p].f=0;
}
void delmin()
{
    int p=spl.fl();
    //while(t[p].son[0])p=t[p].son[0];
    qw(sgt.ask(p));puts("");
    spl.del(p);--len;
    if(!len){root=0;return ;}
    if(p==root)sgt.change(1,n,-1);
    else if(t[p].f-1>=p+1) sgt.change(p+1,t[p].f-1,-1);
    if(p==root)t[root=t[p].son[1]].f=0;
    else {t[t[p].f].son[0]=t[p].son[1];if(t[p].son[1])t[t[p].son[1]].f=t[p].f;}
}
void delmax()
{
    int p=spl.fr();
    //while(t[p].son[1])p=t[p].son[1];
    qw(sgt.ask(p));puts("");
    spl.del(p);--len;
    if(!len){root=0;return ;}
    if(p==root)sgt.change(1,n,-1);
    else if(t[p].f+1<=p-1)sgt.change(t[p].f+1,p-1,-1);
    if(p==root)t[root=t[p].son[0]].f=0;
    else {t[t[p].f].son[1]=t[p].son[0];if(t[p].son[0])t[t[p].son[0]].f=t[p].f;}
}
struct Query{int op,key;}q[N];int a[N];
inline int get(int d)
{
    int l=1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(d<=a[mid])r=mid;
        else l=mid+1;
    }
    return l;
}
int main()
{
    //freopen("splay8.in","r",stdin);
    //freopen("1.ans","w",stdout);
    int m;qr(m);
    for(int i=1;i<=m;i++)
    {
        qr(q[i].op);
        if(q[i].op==1)qr(q[i].key),a[++n]=q[i].key;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++)
        if(q[i].op==1)q[i].key=get(q[i].key);
    for(int i=1;i<=m;i++)
    {
        int op=q[i].op;++cnt;
        if(op==1)ins(q[i].key);
        else if(op==2)romin();
        else if(op==3)romax();
        else if(op==4)delmin();
        else delmax();
    }
    return 0;
}