首先考虑如何不利用树的本身来实现insert,单旋min,max的操作。
insert:
一定是插在前驱或者后继的下面。
用线段树得到前驱后继，
判断一下前驱后继哪一个能插即可。
单旋min:
min一定只有右儿子，并且到爸爸的一条链上都是往左的。
发现单旋后树的形态改变不大，只有右儿子和爸爸接了起来，并且他变成了根。
单旋max同理
旋到根后删除是很简单的。
现在需要支持询问每个点到根的距离。用lct维护即可。
#include<bits/stdc++.h>
using std::sort;
using std::cerr;
using std::endl;
const int N=100010;
struct query
{
int type,x;
}q[N];
int m,i;
int n;
namespace lisan
{
int *q[N];
void push(int &x)
{
scanf("%d",&x);
q[++n]=&x;
}
bool xiao(int *x,int *y)
{
return *x<*y;
}
void work()
{
sort(q+1,q+n+1,xiao);
for(i=1;i<=n;++i) *q[i]=i;
}
};
#define L (i<<1)
#define R (L+1)
bool a[N*3];int d;
void mark(int i)
{
for(i+=d;!a[i];i>>=1)a[i]=1;
}
void clear(int i)
{
a[i+=d]=0;
while(i>>=1)a[i]=a[L]||a[R];
}
int get_min(int i=1)
{
while(i<=d)
if(a[L])i=L;
else i=R;
return i-d;
}
int get_max(int i=1)
{
while(i<=d)
if(a[R])i=R;
else i=L;
return i-d;
}
int get_pre(int i)
{
i+=d;
while(i)
{
if((i&1)&&a[i^1]) { i^=1;break; }
i>>=1;
}
if(!i) return 0;
return get_max(i);
}
int get_suf(int i)
{
i+=d;
while(i)
{
if((!(i&1))&&a[i^1]) { i^=1;break; }
i>>=1;
}
if(!i) return 0;
return get_min(i);
}
namespace lct
{
int f[N],c[N][2],sz[N];
bool root(int x)
{
return x!=c[f[x]][0]&&x!=c[f[x]][1];
}
void up(int x)
{
sz[x]=sz[c[x][0]]+sz[c[x][1]]+1;
}
bool get(int x)
{
return x==c[f[x]][1];
}
void sc(int y,int x,bool d)
{
f[x]=y;
c[y][d]=x;
}
void rot(int x)
{
int y=f[x];bool d=get(x);
if(root(y)) f[x]=f[y];
else sc(f[y],x,get(y));
sc(y,c[x][!d],d);sc(x,y,!d);
up(y);
}
void splay(int x)
{
while(!root(x))
{
int y=f[x];
if(root(y)) { rot(x);break; }
rot(get(y)==get(x)?y:x);rot(x);
}
up(x);
}
void access(int x)
{
int y=0;
while(x)
{
splay(x);
c[x][1]=y;
y=x;
x=f[x];
}
}
int deep(int x)
{
access(x);
splay(x);
return sz[x];
}
/* void del(int rt)
{
splay(rt);
f[c[rt][1]]=0;
}*/
void clear(int x)
{
f[x]=c[x][0]=c[x][1]=0;
}
};
int root,f[N],c[N][2];
void sc(int y,int x,bool d)
{
f[x]=y;
c[y][d]=x;
}
bool get(int x)
{
return x==c[f[x]][1];
}
void ins(int x)
{
if(!root) {root=x;return ;}
int pre=get_pre(x),suf=get_suf(x);
if(!pre||c[pre][1]) //pre不行，选择插在suf左边
{ sc(suf,x,0);lct::f[x]=suf; }
else
{ sc(pre,x,1);lct::f[x]=pre; }
}
int rt;
void change(int x,bool d)
{
if(c[x][d])
{
lct::access(c[x][d]);
if(x==root) { f[root=c[x][d]]=0;lct::f[root]=0; }
else
{sc(f[x],c[x][d],get(x));
lct::f[c[x][d]]=0;
lct::sc(c[x][d],lct::c[x][0],0);
}
}
else
{
if(x==root)root=0;
else lct::f[lct::c[x][0]]=0;
c[f[x]][get(x)]=0;
}
c[x][d]=f[x]=0;
lct::clear(x);
}
void make_root(int x)
{
if(root)
{
sc(x,root,root>x);
lct::splay(root);
lct::f[root]=x;
}
root=x;
}
void rot_min()
{
rt=get_min();
printf("%d\n",lct::deep(rt));
change(rt,1);
if(q[i].type==4) clear(rt);
else make_root(rt);
}
void rot_max()
{
rt=get_max();
printf("%d\n",lct::deep(rt));
change(rt,0);
if(q[i].type==5) clear(rt);
else make_root(rt);
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
scanf("%d",&m);
for(i=1;i<=m;++i)
{
scanf("%d",&q[i].type);
if(q[i].type==1) lisan::push(q[i].x);
}
lisan::work();
for(d=1;d<n;d<<=1);d-=1;
for(i=1;i<=m;++i)
{
//cerr<<i<<endl;
if(i==4)
int kcz=1;
if(q[i].type==1)
{
ins(q[i].x);
mark(q[i].x);
printf("%d\n",lct::deep(q[i].x));
}else
if(q[i].type==2||q[i].type==4) rot_min();
else rot_max();
}
}
鄂公网安备 42010202000505 号