这题难道不是spaly裸题吗？
言归正传QWQ
一看到这个题目，其实第一反应是很懵X的
从来没有见过类似的题目啊，什么(spaly)，单旋。QWQ很懵逼啊
不过，我们可以注意到这么一件事情，就是我们对于树中元素移动的时候，只会移动(min或者max)。
那么会不会有什么性质呢
QWQ
经过手玩，以(max)为栗，我们可以发现我们将这个点单旋到根的话，相当于就是说保持的原树的形态不变，把(max)的左儿子连到(max)的父亲，然后删除这个点，然后把(root)接到(max)的左儿子上。
最小值和最大值同理
这不就是一个(link)和一个(cut)吗QWQ
所以直接可以上(LCT)
每次代价，就是从当前点到根的距离
我们现在考虑怎么插入
有一个结论是，插入的时候一定会插到前驱和后继中深度比较大的那个的对应儿子。
因为因为前驱和后继一定是父子关系，只有深的那个才可能出现合法位置的空儿子
QWQ另外的话就是一些细节了
需要除了(LCT)之外，再维护原树的形态和(fa)的两个数组
然后实时维护一个(root)，表示原树的根。每次操作完都(makeroot)，便于计算路径长度
剩下的还是直接去看代码吧
QWQ
感觉这个题很好啊，思维挺不错的
细节也有不少
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define mk makr_pair
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 3e5+1e2;
struct Node
{
int opt,val;
};
Node a[maxn];
int ch[maxn][3];//LCT中的父子关系
int fa[maxn];
int zuzong[maxn];//spaly中的父子关系
int son[maxn][3];
int n,m;
int rev[maxn],st[maxn],size[maxn];
set<int> s;
int b[maxn];
int cnt;
int root;
int sson(int x)
{
if (ch[fa[x]][0]==x) return 0;
else return 1;
}
bool notroot(int x)
{
return ch[fa[x]][0]==x || ch[fa[x]][1]==x;
}
void update(int x)
{
if (!x) return;
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void reverse(int x)
{
swap(ch[x][0],ch[x][1]);
rev[x]^=1;
}
void pushdown(int x)
{
if(rev[x])
{
if (ch[x][0]) reverse(ch[x][0]);
if (ch[x][1]) reverse(ch[x][1]);
rev[x]=0;
}
}
void rotate(int x)
{
int y=fa[x],z=fa[y];
int b=sson(x),c=sson(y);
if (notroot(y)) ch[z][c]=x;
fa[x]=z;
ch[y][b]=ch[x][!b];
fa[ch[x][!b]]=y;
ch[x][!b]=y;
fa[y]=x;
update(y);
update(x);
}
void splay(int x)
{
int y=x,cnt=0;
st[++cnt]=y;
while (notroot(y)) y=fa[y],st[++cnt]=y;
while (cnt) pushdown(st[cnt--]);
while (notroot(x))
{
int y=fa[x],z=fa[y];
int b=sson(x),c=sson(y);
if (notroot(y))
{
if(b==c) rotate(y);
else rotate(x);
}
rotate(x);
//cout<<x<<endl;
}
update(x);
}
void access(int x)
{
for (int y=0;x;y=x,x=fa[x])
{
splay(x);
ch[x][1]=y;
update(x);
}
}
void makeroot(int x)
{
access(x);
splay(x);
reverse(x);
}
int findroot(int x)
{
access(x);
splay(x);
while (ch[x][0])
{
pushdown(x);
x=ch[x][0];
}
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void link(int x,int y)
{
if (!x || !y) return;
makeroot(x);
if (findroot(y)!=x)
fa[x]=y;
}
void cut(int x,int y)
{
if (!x || !y) return;
split(x,y);
if (ch[x][0] || ch[x][1] || fa[x]!=y || ch[y][1]) return;
fa[x]=ch[y][0]=0;
update(y);
}
int query(int x)
{
access(x);
splay(x);
return size[x];
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
a[i].opt=read();
if (a[i].opt==1) a[i].val=read(),b[++cnt]=a[i].val;
}
sort(b+1,b+1+cnt);
for (int i=1;i<=n;i++)
if(a[i].opt==1) a[i].val=lower_bound(b+1,b+1+cnt,a[i].val)-b; //离散化，权值既是编号
for (int i=1;i<=n;i++)
{
if (a[i].opt==1)
{
int lyf,ymh=0;
if (s.size()==0)
{
cout<<1<<"
";
s.insert(a[i].val);
root=a[i].val;
continue;
}
set<int> :: iterator now = s.upper_bound(a[i].val);
if(now!=s.end())
{
//ymh=max(ymh,query(*now));
if (query(*now)>=ymh) ymh=query(*now),lyf=*now;
}
if(now!=s.begin())
{
--now;
if (query(*now)>=ymh) ymh=query(*now),lyf=*now;
}
//插入的时候，应该找到前驱和后继深度较深的那个，然后插入
//因为前驱和后继一定是父子关系，只有深的那个 才可能出现合法位置的空儿子
cout<<ymh+1<<"
";
zuzong[a[i].val]=lyf;
son[lyf][lyf<a[i].val]=a[i].val;
s.insert(a[i].val);
link(a[i].val,lyf);
}
if (a[i].opt==2)
{
int now = *(s.begin());
int faa = zuzong[now];
int ss = son[now][1];
cout<<query(now)<<"
";
if (now==root) continue;
cut(now,faa);
cut(now,ss);
link(ss,faa);
link(root,now);
zuzong[root]=now;
zuzong[now]=0;
son[now][1]=root;
zuzong[ss]=faa;
son[faa][0]=ss;
root=now;
//找到最小值，然后手动修改原树的父子关系，然后暴力link和cut
}
if (a[i].opt==3)
{
int now = *(s.rbegin());
int faa = zuzong[now];
int ss = son[now][0];
cout<<query(now)<<"
";
if (now==root) continue;
cut(now,faa);
cut(now,ss);
link(ss,faa);
link(root,now);
zuzong[root]=now;
zuzong[now]=0;
son[now][0]=root;
zuzong[ss]=faa;
son[faa][1]=ss;
root=now;
//和最小值同理
}
if(a[i].opt==4)
{
set<int> :: iterator pos = s.begin();
int now = *(s.begin());
int faa = zuzong[now];
int ss = son[now][1];
cout<<query(now)<<"
";
cut(now,faa);
cut(now,ss);
link(ss,faa);
zuzong[ss]=faa;
son[faa][0]=ss;
son[now][0]=son[now][1]=zuzong[now]=0;
s.erase(now);
if (root==now) root=ss;
}
if (a[i].opt==5)
{
int now = *(s.rbegin());
int faa = zuzong[now];
int ss = son[now][0];
cout<<query(now)<<"
";
cut(now,faa);
cut(now,ss);
link(ss,faa);
zuzong[ss]=faa;
son[faa][1]=ss;
son[now][0]=son[now][1]=zuzong[now]=0;
s.erase(now);
if (root==now) root=ss;
}
makeroot(root);
}
return 0;
}