一道码力题,调了我一天。
把最小的元素$x$旋到根,深度改变的只有$x$变为$1$,以及除$x$子树的所有点深度$+1$
最大元素一样的。
删掉最小元素$x$,深度改变的只有$x$子树(深度$-1$)。
插入的话,因为二叉搜索树的连续性,要么将$x$插入在它的前驱,要么后继,取决于哪个深度大。
细节的话,注意父亲结点是否存在,子树是否存在。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=1e9+7,N=1e5+10;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
struct Splay
{
struct node{int f,son[2],d;}t[N];int len,root;
void add(int d,int f){t[++len]=(node){f,{0,0},d};t[f].son[d>t[f].d]=len;}
void rotate(int p,int w)
{
int f=t[p].f,gf=t[f].f;
int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
r=p;R=gf;t[R].son[t[R].son[1]==f]=r;t[r].f=R;
r=f;R=p;t[R].son[w]=r;t[r].f=R;
}
void splay(int p,int rt)
{
while(t[p].f!=rt)
{
int f=t[p].f,gf=t[f].f;
if(gf==rt)rotate(p,t[f].son[0]==p);
else
{
if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
else rotate(f,0),rotate(p,0);
}
}
if(!rt)root=p;
}
int get_id(int d)
{
int p=root;
while(t[p].d!=d)
{
if(d<t[p].d)
{
if(!t[p].son[0])break;
p=t[p].son[0];
}
if(d>t[p].d)
{
if(!t[p].son[1])break;
p=t[p].son[1];
}
}
return p;
}
void ins(int d)
{
if(!root){add(d,0);root=len;return ;}
int p=get_id(d);add(d,p);splay(len,0);
}
void del(int d)
{
int p=get_id(d);splay(p,0);
if(!t[p].son[0]&&!t[p].son[1])root=0,len=0;
else if(t[p].son[1]&&!t[p].son[0])t[root=t[p].son[1]].f=0;
else if(t[p].son[0]&&!t[p].son[1])t[root=t[p].son[0]].f=0;
else
{
int R=t[p].son[0];while(t[R].son[1])R=t[R].son[1];splay(R,p);
int r=t[p].son[1];t[R].son[1]=r;t[r].f=R;t[root=R].f=0;splay(R,0);
}
}
int nxt(int d)
{
int p=get_id(d);splay(p,0);
if(t[p].d<=d&&t[p].son[1])
for(p=t[p].son[1];t[p].son[0];p=t[p].son[0]);
if(t[p].d<=d)return 0;
return t[p].d;
}
int prv(int d)
{
int p=get_id(d);splay(p,0);
if(t[p].d>=d&&t[p].son[0])
for(p=t[p].son[0];t[p].son[1];p=t[p].son[1]);
if(t[p].d>=d)return 0;
return t[p].d;
}
int fl(){int p=root;while(t[p].son[0])p=t[p].son[0];return t[p].d;}
int fr(){int p=root;while(t[p].son[1])p=t[p].son[1];return t[p].d;}
}spl;
int n;
struct SGT
{
int c[N];
SGT(){memset(c,0,sizeof(c));}
inline void add(int x,int d){for(;x<=n;x+=x&-x)c[x]+=d;}
inline void change(int l,int r,int d){add(l,d);add(r+1,-d);}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
inline void modify(int x,int d)
{
int w=ask(x);d=d-w;
add(x,d),add(x+1,-d);
}
/*struct node{int w,ad;}t[N<<2];
void pushdown(int p)
{
if(t[p].ad)
t[p<<1].ad+=t[p].ad,t[p<<1|1].ad+=t[p].ad,
t[p<<1].w+=t[p].ad,t[p<<1|1].w+=t[p].ad,t[p].ad=0;
}
void modify(int p,int l,int r,int x,int d)
{
if(l==r){t[p].w=d;return ;}
pushdown(p);int mid=l+r>>1;
if(x<=mid)modify(p<<1,l,mid,x,d);
else modify(p<<1|1,mid+1,r,x,d);
}
void change(int p,int l,int r,int x,int ad)
{
if(l==r){t[p].w+=ad;return ;}
pushdown(p);int mid=l+r>>1;
if(x<=mid)change(p<<1,l,mid,x,ad);
else change(p<<1|1,mid+1,r,x,ad);
}
void change(int p,int l,int r,int L,int R,int ad)
{
if(L<=l&&R>=r){t[p].ad+=ad,t[p].w+=ad;return ;}
pushdown(p);int mid=l+r>>1;
if(L<=mid)change(p<<1,l,mid,L,R,ad);
if(R>mid)change(p<<1|1,mid+1,r,L,R,ad);
}
int query(int p,int l,int r,int x)
{
if(l==r)return t[p].w;
pushdown(p);int mid=l+r>>1;
if(x<=mid)return query(p<<1,l,mid,x);
return query(p<<1|1,mid+1,r,x);
}*/
}sgt;
struct node{int f,son[2];}t[N];int root,len,cnt;
void ins(int p)
{
++len;spl.ins(p);
if(!root){root=p;t[root].f=0;sgt.modify(p,1);puts("1");return ;}
int nxt=spl.nxt(p),prv=spl.prv(p),w1=0,w2=0;
if(nxt)w1=sgt.ask(nxt);
if(prv)w2=sgt.ask(prv);
if(w1>w2)t[nxt].son[0]=p,t[p].f=nxt,sgt.modify(p,w1+1);
else t[prv].son[1]=p,t[p].f=prv,sgt.modify(p,w2+1);
qw(max(w1+1,w2+1));puts("");
}
void romin()
{
int p=spl.fl();
//while(t[p].son[0])p=t[p].son[0];
qw(sgt.ask(p));puts("");
if(p==root)return ;
sgt.change(1,n,1);
if(p+1<=t[p].f-1)sgt.change(p+1,t[p].f-1,-1);
sgt.modify(p,1);
t[t[p].f].son[0]=t[p].son[1];if(t[p].son[1])t[t[p].son[1]].f=t[p].f;
t[p].son[1]=root;t[root].f=p;root=p;t[p].f=0;
}
void romax()
{
int p=spl.fr();
//while(t[p].son[1])p=t[p].son[1];
qw(sgt.ask(p));puts("");
if(p==root)return ;
sgt.change(1,n,1);
if(t[p].f+1<=p-1)sgt.change(t[p].f+1,p-1,-1);
sgt.modify(p,1);
t[t[p].f].son[1]=t[p].son[0];if(t[p].son[0])t[t[p].son[0]].f=t[p].f;
t[p].son[0]=root;t[root].f=p;root=p;t[p].f=0;
}
void delmin()
{
int p=spl.fl();
//while(t[p].son[0])p=t[p].son[0];
qw(sgt.ask(p));puts("");
spl.del(p);--len;
if(!len){root=0;return ;}
if(p==root)sgt.change(1,n,-1);
else if(t[p].f-1>=p+1) sgt.change(p+1,t[p].f-1,-1);
if(p==root)t[root=t[p].son[1]].f=0;
else {t[t[p].f].son[0]=t[p].son[1];if(t[p].son[1])t[t[p].son[1]].f=t[p].f;}
}
void delmax()
{
int p=spl.fr();
//while(t[p].son[1])p=t[p].son[1];
qw(sgt.ask(p));puts("");
spl.del(p);--len;
if(!len){root=0;return ;}
if(p==root)sgt.change(1,n,-1);
else if(t[p].f+1<=p-1)sgt.change(t[p].f+1,p-1,-1);
if(p==root)t[root=t[p].son[0]].f=0;
else {t[t[p].f].son[1]=t[p].son[0];if(t[p].son[0])t[t[p].son[0]].f=t[p].f;}
}
struct Query{int op,key;}q[N];int a[N];
inline int get(int d)
{
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
if(d<=a[mid])r=mid;
else l=mid+1;
}
return l;
}
int main()
{
//freopen("splay8.in","r",stdin);
//freopen("1.ans","w",stdout);
int m;qr(m);
for(int i=1;i<=m;i++)
{
qr(q[i].op);
if(q[i].op==1)qr(q[i].key),a[++n]=q[i].key;
}
sort(a+1,a+n+1);
for(int i=1;i<=m;i++)
if(q[i].op==1)q[i].key=get(q[i].key);
for(int i=1;i<=m;i++)
{
int op=q[i].op;++cnt;
if(op==1)ins(q[i].key);
else if(op==2)romin();
else if(op==3)romax();
else if(op==4)delmin();
else delmax();
}
return 0;
}
最后一次更新于2020-04-23
0 条评论