Spaly竟然不用写Splay……
首先我们发现每次zig的都是极小值，换句话说这个点会被一直zig到根
我们考虑zig到根后所有点的深度变化，画个图就会发现现在这个点本身深度变成(1)，子树内的点深度不变，其余的点深度加(1)
同理删除这个点时就是子树内的点深度减(1)，zag的情况同理
那么我们就轻松地完成了2,3,4,5操作了，考虑插入的深度怎么快速求
由于BST中序遍历有序的性质以及在每个点选择左右儿子的类二分性，我们发现在插入一个点时一定会经过它的前驱和后继
那么很简单，我们找出前驱和后继中深度较大的点，这个点就是插入点的父节点
所以我们再用splayset维护一下前驱后继即可，考虑我们目前要进行的操作：
区间修改，单点赋值/查询，显然可以用树状数组维护
#include<cstdio>
#include<algorithm>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int rt,m,opt[N],a[N],rst[N],tot,fa[N],ch[N][2],x,pre,nxt,dp,dn;
set <int> s; set <int>:: iterator it;
class Tree_Array
{
private:
#define lowbit(x) (x&-x)
int bit[N];
inline void upt(RI x,CI y)
{
for (;x<=tot;x+=lowbit(x)) bit[x]+=y;
}
public:
inline void add(CI x,CI y,CI z)
{
upt(x,z); upt(y+1,-z);
}
inline int get(RI x,int ret=0)
{
for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
}
inline void cvr(CI x,CI t)
{
int dlt=t-get(x); add(x,x,dlt);
}
#undef lowbit
}BIT;
inline void connect(CI x,CI y,CI d)
{
ch[fa[x]=y][d]=x;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&m),i=1;i<=m;++i)
if (scanf("%d",&opt[i]),opt[i]==1) scanf("%d",&a[i]),rst[++tot]=a[i];
for (sort(rst+1,rst+tot+1),tot=unique(rst+1,rst+tot+1)-rst-1,i=1;i<=m;++i)
{if (i==8)
{
bool D=1;
}
switch (opt[i])
{
case 1:
a[i]=lower_bound(rst+1,rst+tot+1,a[i])-rst;
if (rt)
{
it=s.lower_bound(a[i]); if (it==s.begin()) pre=0; else pre=*(--it);
it=s.upper_bound(a[i]); if (it==s.end()) nxt=0; else nxt=*it;
dp=BIT.get(pre); dn=BIT.get(nxt); s.insert(a[i]);
if (dp>=dn) BIT.cvr(a[i],dp+1),printf("%d
",dp+1),connect(a[i],pre,1);
else BIT.cvr(a[i],dn+1),printf("%d
",dn+1),connect(a[i],nxt,0);
} else s.insert(a[i]),rt=a[i],puts("1"),BIT.cvr(a[i],1); break;
case 2:
x=*s.begin(); printf("%d
",BIT.get(x));
if (fa[x]) BIT.cvr(x,1),BIT.add(fa[x],tot,1),connect(ch[x][1],fa[x],0),connect(rt,x,1),fa[rt=x]=0; break;
case 3:
it=s.end(); x=*(--it); printf("%d
",BIT.get(x));
if (fa[x]) BIT.cvr(x,1),BIT.add(1,fa[x],1),connect(ch[x][0],fa[x],1),connect(rt,x,0),fa[rt=x]=0; break;
case 4:
x=*s.begin(); printf("%d
",BIT.get(x)); s.erase(x);
BIT.add(x+1,fa[x]?fa[x]-1:tot,-1); fa[(fa[x]?ch[fa[x]][0]:rt)=ch[x][1]]=fa[x]; break;
case 5:
it=s.end(); x=*(--it); printf("%d
",BIT.get(x)); s.erase(x);
BIT.add(fa[x]?fa[x]+1:1,x-1,-1); fa[(fa[x]?ch[fa[x]][1]:rt)=ch[x][0]]=fa[x]; break;
}}
return 0;
}