题意
有一个单旋的 \(splay\)，叫做 \(spaly\)。节点数 \(n\le 10^5\)
以下几种操作，共 \(m\) 次。
- \(key\) 加入一个值为 \(key\) 的点，\(a\le10^9\)，任意两次 \(1\) 操作的 \(key\) 互不相同。
- 将最小值旋到根，输出旋转前的深度。
- 将最大值旋到根，输出旋转前的深度。
- 将最小值旋到根，输出旋转前的深度，然后把根删除。
- 将最小值旋到根，输出旋转前的深度，然后把根删除。
\(n,m\le10^5\)。
思路
先把所有关键码离散化。
用 set 维护点，线段树维护深度，用数组维护 spaly 的形态。
插入 \(a\)
如果没有根，把这个节点当作根。
否则找到 \(a\) 的前驱 \(p\) 和后继 \(q\)，分类讨论：
- 前驱后继都存在
那么祂们中的某一个一定是另一个的祖先。如果 \(p\) 是祖先，那么 \(p\) 的右儿子一定有值，\(q\) 的左儿子一定是空的，那么把 \(a\) 接到 \(q\) 的左儿子上。如果 \(q\) 是祖先，同理，把 \(a\) 接到 \(p\) 的右儿子上。 - 只存在前驱
把 \(a\) 接到 \(p\) 的右儿子上。 - 只有后继
把 \(a\) 接到 \(q\) 的左儿子上。
找前驱和后继可以直接在set中查询，插入后 \(a\) 的深度即为祂父亲的深度加 \(1\)，树的形态直接修改。
单旋最小值
找到最小值对应的点 \(x\)。
形态
\(x\) 一定只有右儿子（或没有），把祂接到 \(x\) 的父亲的左儿子上。
把 \(x\) 的右儿子设为当前的根，父亲设为空。
深度
\(x\) 的右子树中的点深度不变，\(x\) 的深度变成 \(1\)，其祂点的深度加 \(1\)。
可以全局深度加 \(1\)，然后给 \(x\) 的右子树减 \(1\)，最后把 \(x\) 的深度赋值为 \(1\)。
由于一个子树内的编号都是连续的，所以用线段树是好维护的。
单旋最大值
同理。
单旋删除最小值
先执行单旋最小值，然后把跟和祂的儿子断开，全局深度减 \(1\)。
单旋删除最大值
同理。
代码
/*
Luogu P3721 [AHOI2017/HNOI2017] 单旋
2026-03-21
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=100010;
int n,op[maxn],a[maxn],p[maxn],cnt_p;
class Segment_Tree{
private:int t[maxn*4];void down(int u){t[u<<1]+=t[u],t[u<<1|1]+=t[u];t[u]=0;}void update1(int u,int l,int r,int d,int z){if(l>d||r<d) return ;if(l==r){t[u]=z;return ;}down(u);int mid=l+r>>1;update1(u<<1,l,mid,d,z),update1(u<<1|1,mid+1,r,d,z);}void update2(int u,int l,int r,int ll,int rr,int z){if(ll>r||rr<l) return ;if(ll<=l&&r<=rr){t[u]+=z;return ;}down(u);int mid=l+r>>1;update2(u<<1,l,mid,ll,rr,z),update2(u<<1|1,mid+1,r,ll,rr,z);}int query(int u,int l,int r,int d){if(l>d||r<d) return 0;if(l==r) return t[u];down(u);int mid=l+r>>1;return query(u<<1,l,mid,d)+query(u<<1|1,mid+1,r,d);}
public:void update1(int d,int z){update1(1,1,n,d,z);}void update2(int l,int r,int z){update2(1,1,n,l,r,z);}int query(int d){return query(1,1,n,d);}
}t;
set<int>s;
int rt=0,ch[maxn][2],fa[maxn];
int insert(int x){s.insert(x);if(rt==0){rt=x;t.update1(x,1);return 1;}auto w=s.lower_bound(x);if(w!=s.begin()){w--;if(!ch[*w][1]) ch[fa[x]=*w][1]=x;w++;}if(!fa[x]) w++,ch[fa[x]=*w][0]=x;int ans=t.query(fa[x])+1;t.update1(x,ans);return ans;
}
int find_min(){int x=*s.begin(),ans=t.query(x);if(x==rt) return ans;t.update2(x+1,fa[x]-1,-1);t.update2(1,n,1);ch[fa[x]][0]=ch[x][1];fa[ch[x][1]]=fa[x];ch[x][1]=rt;fa[rt]=x;rt=x;t.update1(x,1);return ans;
}
int find_max(){int x=*s.rbegin(),ans=t.query(x);if(x==rt) return ans;t.update2(fa[x]+1,x-1,-1);t.update2(1,n,1);ch[fa[x]][1]=ch[x][0];fa[ch[x][0]]=fa[x];ch[x][0]=rt;fa[rt]=x;rt=x;t.update1(x,1);return ans;
}
void del_min(){write(find_min());t.update2(1,n,-1);s.erase(rt);fa[ch[rt][1]]=0;rt=ch[rt][1];
}
void del_max(){write(find_max());t.update2(1,n,-1);s.erase(rt);fa[ch[rt][0]]=0;rt=ch[rt][0];
}
signed main(){read(n);for(int i=1;i<=n;i++){read(op[i]);if(op[i]==1) read(a[i]),p[++cnt_p]=a[i];}sort(p+1,p+1+cnt_p);cnt_p=unique(p+1,p+1+cnt_p)-p-1;for(int i=1;i<=n;i++) if(op[i]==1) a[i]=lower_bound(p+1,p+1+cnt_p,a[i])-p;for(int i=1;i<=n;i++){if(op[i]==1) write(insert(a[i]));if(op[i]==2) write(find_min());if(op[i]==3) write(find_max());if(op[i]==4) del_min();if(op[i]==5) del_max();write("\n");}return 0;
}