题目：https://www.luogu.org/problemnew/show/P3721

手玩一下即可AC此题。

结论：插入x后，x要么会成为x的前驱的右儿子，要么成为x的后继的左儿子，这取决于它的前驱和后继的深度。

证明：首先可以证明的是，x的前驱和后继一定存在祖先与后代的关系，因为如果不存在此关系，它们的LCA一定和双方更接近。

然后这个结论画画图就比较显然了。

结论：单旋删除最小值后，它连向根节点的这条路径不发生变化，手玩即可证明，改变的只有它的儿子。

那么这个题就显然可以用LCT来维护，查询深度也很简单。

#include<iostream>

#include<cctype>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<set>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#define N 330000

#define L 300000

#define eps 1e-7

#define inf 1e9+7

#define db double

#define ll long long

#define ldb long double

using namespace std;

inline int read()

{

	char ch=0;

	int x=0,flag=1;

	while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}

	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*flag;

}

#define lson son[x][0]

#define rson son[x][1]

int root,v[N],f[N],st[N],flag[N],sumv[N],son[N][2];

void pushup(int x){sumv[x]=sumv[lson]+sumv[rson]+1;}

void update(int x){flag[x]^=1;swap(lson,rson);}

void pushdown(int x){if(!flag[x])return;if(lson)update(lson);if(rson)update(rson);flag[x]=0;}

bool get(int x){return son[f[x]][1]==x;}

bool isroot(int x){return (son[f[x]][0]!=x)&&(son[f[x]][1]!=x);}

void rotate(int x)

{

	int y=f[x],z=f[y],tx=get(x),ty=get(y),p=son[x][!tx];

	if(!isroot(y))son[z][ty]=x;son[x][!tx]=y;son[y][tx]=p;

	if(p)f[p]=y;f[y]=x;f[x]=z;pushup(y);pushup(x);

}

void splay(int x)

{

	int cnt=0,tmp=x;

	st[++cnt]=x;

	while(!isroot(x))st[++cnt]=f[x],x=f[x];

	for(int i=cnt;i>=1;i--)pushdown(st[i]);

	x=tmp;

	while(!isroot(x))

	{

		int y=f[x];

		if(!isroot(y))rotate(get(x)==get(y)?y:x);

		rotate(x);

	}

	pushup(x);

}

void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y,pushup(x);}

void makeroot(int x){access(x);splay(x);update(x);}

void link(int x,int y){if(!x||!y)return;makeroot(x);f[x]=y;}

void cut(int x,int y){if(!x||!y)return;makeroot(x);access(y);splay(y);f[x]=son[y][0]=0;pushup(y);}

int dep(int x){makeroot(root);access(x);splay(x);return sumv[x];}

set<int>S;

set<int>::iterator it;

int opt[N],w[N],W[N],fa[N],lc[N],rc[N];

int main()

{

	int m=read(),num=0;

	for(int i=1;i<=m;i++)

	{

		opt[i]=read();

		if(opt[i]==1)w[i]=W[++num]=read();

	}

	sort(W+1,W+num+1);num=unique(W+1,W+num+1)-W-1;

	for(int i=1;i<=m;i++)if(opt[i]==1)w[i]=lower_bound(W+1,W+num+1,w[i])-W;

	for(int i=1;i<=m;i++)

	{

		lc[0]=rc[0]=fa[0]=fa[root]=0;

		int flag=opt[i];

		if(flag==1)

		{

			int x=w[i],p,q;

			S.insert(x);it=S.find(x);

			if(it==S.begin())p=-1;else p=*(--S.lower_bound(x));

			if(it==(--S.end()))q=-1;else q=*(S.upper_bound(x));

			if(p==-1&&q==-1){root=x;printf("1\n");continue;}

			if(p==-1||dep(p)<dep(q))link(x,q),lc[q]=x,fa[x]=q;

			else link(x,p),rc[p]=x,fa[x]=p;

			printf("%d\n",dep(x));

		}

		if(flag==2||flag==4)

		{

			int x=*S.begin(),p=rc[x],q=fa[x];

			printf("%d\n",dep(x));

			if(x!=root)

			{

				cut(x,p);cut(x,q);link(p,q);link(x,root);

				lc[q]=p;if(p)fa[p]=q;rc[x]=root;fa[x]=0;fa[root]=x;root=x;

			}

		}

		if(flag==3||flag==5)

		{

			int x=*S.rbegin(),p=lc[x],q=fa[x];

			printf("%d\n",dep(x));

			if(x!=root)

			{

				cut(x,p);cut(x,q);link(p,q);link(x,root);

				rc[q]=p;if(p)fa[p]=q;lc[x]=root;fa[x]=0;fa[root]=x;root=x;

			}

		}

		if(flag==4)

		{

			int x=*S.begin(),p=rc[x];

			if(p)cut(x,p),rc[x]=fa[p]=0;

			root=p;S.erase(x);

		}

		if(flag==5)

		{

			int x=*S.rbegin(),p=lc[x];

			if(p)cut(x,p),lc[x]=fa[p]=0;

			root=p;S.erase(x);

		}

	}

	return 0;

}