BZOJ
Luogu
題目太長了，就不放了。
題解
首先聲明一點，無論是splay還是spaly，插入一個新的元素，都要rotate到根！是以說題目也算是給了一個錯誤示範吧。
我們發現把最值旋轉到根并不會給這棵spaly造成多大的形态改變，是以考慮用LCT維護這個spaly的形态。
每次插入的時候我們用一個Set來找出插入元素的前驅後繼。可以證明，一定會插在前驅或者是後繼的對應左右兒子上。判斷一下插入即可。除了LCT裡的splay外，還要維護一下原樹中(spaly中)的父親、左右兒子關系。
code
細節。。還好吧
我tm又雙叒叕把一個l打成r了
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
const int N = 100005;
int fa[N],ls[N],rs[N],rev[N],sz[N],Stack[N],top;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
bool isroot(int x){return ls[fa[x]]!=x&&rs[fa[x]]!=x;}
void pushup(int x){sz[x]=sz[ls[x]]+sz[rs[x]]+1;}
void pushdown(int x){if (!rev[x]) return;swap(ls[x],rs[x]);rev[ls[x]]^=1;rev[rs[x]]^=1;rev[x]=0;}
void R_rotate(int x)
{
int y=fa[x],z=fa[y];
ls[y]=rs[x];
if (rs[x]) fa[rs[x]]=y;
fa[x]=z;
if (!isroot(y)) if (y==ls[z]) ls[z]=x;else rs[z]=x;
rs[x]=y;fa[y]=x;
pushup(y);
}
void L_rotate(int x)
{
int y=fa[x],z=fa[y];
rs[y]=ls[x];
if (ls[x]) fa[ls[x]]=y;
fa[x]=z;
if (!isroot(y)) if (y==ls[z]) ls[z]=x;else rs[z]=x;
ls[x]=y;fa[y]=x;
pushup(y);
}
void splay(int x)
{
Stack[top=1]=x;
for (int i=x;!isroot(i);i=fa[i])
Stack[++top]=fa[i];
while (top) pushdown(Stack[top--]);
while (!isroot(x))
{
int y=fa[x],z=fa[y];
if (isroot(y))
if (x==ls[y]) R_rotate(x);
else L_rotate(x);
else
if (y==ls[z])
if (x==ls[y]) R_rotate(y),R_rotate(x);
else L_rotate(x),R_rotate(x);
else
if (x==ls[y]) R_rotate(x),L_rotate(x);
else L_rotate(y),L_rotate(x);
}
pushup(x);
}
void access(int x){for (int y=0;x;y=x,x=fa[x]) splay(x),rs[x]=y,pushup(x);}
void makeroot(int x){access(x);splay(x);rev[x]^=1;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);fa[x]=y;}
void cut(int x,int y){split(x,y);fa[x]=ls[y]=0;}
map<int,int>M;
set<int>S;
int m,tot,root,ff[N],lson[N],rson[N];
void Insert(int x)
{
int now=++tot;
M[x]=now;
if (S.empty())
{
S.insert(x);
root=now;
puts("1");
return;
}
set<int>::iterator t=S.upper_bound(x);
if (t==S.end()||lson[M[*t]])
{
--t;
int father=M[*t];
link(now,father);rson[father]=now;ff[now]=father;
}
else
{
int father=M[*t];
link(now,father);lson[father]=now;ff[now]=father;
}
S.insert(x);
split(now,root);
printf("%d\n",sz[root]);
}
void Spl_Min()
{
int x=M[*S.begin()];
if (x==root) {puts("1");return;}
split(x,root);printf("%d\n",sz[root]);
cut(x,ff[x]);if (rson[x]) cut(x,rson[x]);
link(x,root);if (rson[x]) link(ff[x],rson[x]);
lson[ff[x]]=rson[x];if (rson[x]) ff[rson[x]]=ff[x];
ff[x]=0;ff[root]=x;rson[x]=root;
root=x;
}
void Spl_Max()
{
int x=M[*--S.end()];
if (x==root) {puts("1");return;}
split(x,root);printf("%d\n",sz[root]);
cut(x,ff[x]);if (lson[x]) cut(x,lson[x]);
link(x,root);if (lson[x]) link(ff[x],lson[x]);
rson[ff[x]]=lson[x];if (lson[x]) ff[lson[x]]=ff[x];
ff[x]=0;ff[root]=x;lson[x]=root;
root=x;
}
void Del_Min()
{
int x=M[*S.begin()];
if (x==root)
{
puts("1");
if (rson[x]) cut(x,rson[x]);
ff[root=rson[x]]=0;
S.erase(S.begin());
return;
}
split(x,root);printf("%d\n",sz[root]);
cut(x,ff[x]);if (rson[x]) cut(x,rson[x]);
if (rson[x]) link(ff[x],rson[x]);
lson[ff[x]]=rson[x];if (rson[x]) ff[rson[x]]=ff[x];
S.erase(S.begin());
}
void Del_Max()
{
int x=M[*--S.end()];
if (x==root)
{
puts("1");
if (lson[x]) cut(x,lson[x]);
ff[root=lson[x]]=0;
S.erase(--S.end());
return;
}
split(x,root);printf("%d\n",sz[root]);
cut(x,ff[x]);if (lson[x]) cut(x,lson[x]);
if (lson[x]) link(ff[x],lson[x]);
rson[ff[x]]=lson[x];if (lson[x]) ff[lson[x]]=ff[x];
S.erase(--S.end());
}
int main()
{
m=gi();
while (m--)
{
int opt=gi();
if (opt==1) Insert(gi());
if (opt==2) Spl_Min();
if (opt==3) Spl_Max();
if (opt==4) Del_Min();
if (opt==5) Del_Max();
}
return 0;
}
轉載于:https://www.cnblogs.com/zhoushuyu/p/8149091.html