lp3285 SCOI2014 方伯伯的OJ

题目要求维护一个编号序列和一个排名序列,并支持四种操作:
1.按照编号修改编号,并返回该编号的排名。
2.将一个节点的排名提升到第一个。
3.将一个节点的排名降低到最后一个。
4.查询某个排名的编号。
很显然是用Splay维护排名,然后开一个数组存编号咯。
然而我们观察到这一题的数据范围是n<=10^8,那么用上述的方法显然会MLE。
故而我们考虑一个Splay节点「真的维护」一个区间。然后每一次要用到一个新的点就把原有的区间剖开。
而数组存编号也就很套路地换成map存编号。
【冬天来了手都在发抖啊】
续:这一题是我在190103的时候写完的,然而直到191003我才调出来。期间经过了十个月。
调试的突破性进展来自于对调试工具的学习使用,这使得我在巨大数据的情况下得以想办法调试。
我首先发现了size发生了错误,进而发现某个节点的size不等于其两孩子的大小之和加上它本身的大小。然后,经由此处,我发现有个节点的相邻节点是一个大小为空的节点,进而发现这个节点在被分配下标之前就被访问了。
最终,我注意到它第一次出现所相接的节点,并发现这个数事实上是一个标号。
紧接着我就顺利地调出另一个错,并通过了此题。
注意点:
1.对于空节点的情况一定要认真考虑,因为如果空节点操作不慎的话很可能会导致一些莫名其妙的错误。
2.要注意适时更新节点。
3.千万不要搞混「标号」和「排名」!!!!!!
4.如果一个点本来就是排名最后的点而要移到排名最后,有可能会出错。

#include<iostream>
#include<cstdio>
#include<map>
#define error(X) printf("ERROR: %d",X)
#define debug(P) printf("(%d):%d,%d,sn:[%d,%d],FA:%d,SZ:%d\n",P,tr[P].l,tr[P].r,tr[P].sn[0],tr[P].sn[1],tr[P].fa,tr[P].sz);

bool bo=0;
class Splay{
	public:
		class Node{
			public:
				int l;
				int r;
				int sz;
				int sn[2];
				int fa;
				inline void set(int L,int R,int FA){
					l=L,r=R,fa=FA,sz=R-L+1,sn[0]=sn[1]=0;
				}
		};
		//i表示mp[i]这个节点的右端点的标号。 
		std::map<int,int> mp;
		Node tr[400005];
		int cnt,rt;
		//寻找当前节点与父亲的关系。 
		inline int fndD(int X){
			return tr[tr[X].fa].sn[1]==X;
		}
		//更新当前节点。 
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].r-tr[X].l+1;
//			if(X==10619&&tr[X].sz<=30){prnt(tr[X].fa);}
		}
		//旋转套装。 
		inline void splayOne(int X){
			if(!X){return;}
			int D=fndD(X),D2=fndD(tr[X].fa);
//			if(X==65505||tr[X].fa==65505||tr[tr[X].fa].sn[D^1]==65505){
//				puts("FKFKFK");
//				printf("X");debug(X);
//				printf("FA");debug(tr[X].fa);
//				printf("BR");debug(tr[tr[X].fa].sn[D^1]);
//			}
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].sn[D^1]].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayTwo(int X){
//			if(bo&&X==38190){debug(X);}
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
		}
		inline void splayRnw(int X){
			while(tr[X].fa){splayTwo(X);}
			rt=X;
		}
//		inline void splayRnw(int X){
//			while(tr[X].fa){
//				int F=tr[X].fa,FF=tr[tr[X].fa].fa;
//				if(!FF)
//			}
//		}
		//找到排名为X的元素。 
		inline int fnd(int X){
			int P=rt;
			while(P){
				if(X>tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1){
					X-=tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1;
					P=tr[P].sn[1];
				}else if(X>tr[tr[P].sn[0]].sz){
					X-=tr[tr[P].sn[0]].sz;
					splayRnw(P);
//					debug(P);
					return tr[P].l+X-1;
				}else{
					P=tr[P].sn[0];
				}
			}
			return -1; 
		}
		//开一个新节点,以X为它的父亲。 
		inline int nwlc(int X,int L,int R){
			int P=++cnt;
//			if(P==65505){
//				printf("START:");
//				debug(P);
//			}
			tr[P].set(L,R,X);
			return P;
		}
		//将编号为X的节点单独弄成一个新的节点,然后将它的两个子节点接到它的左右,并更改相应的编号的映射 
		inline int split(int P,int X){
			if(tr[P].l==tr[P].r){return P;}
			if(P==-1){return error(192600404),192600404;}
			if(X>tr[P].l){
				int L=tr[P].sn[0];
				L?(cut(L),0):(tr[0].fa=0);
				tr[P].sn[0]=nwlc(P,tr[P].l,X-1);
				L?(cnnct(L,tr[P].sn[0],0),0):0;
				mp[X-1]=tr[P].sn[0];
//				updt(tr[P].sn[0]);
			}
			if(X<tr[P].r){
				int R=tr[P].sn[1];
				R?(cut(R),1):(tr[0].fa=0);
				tr[P].sn[1]=nwlc(P,X+1,tr[P].r);
				R?(cnnct(R,tr[P].sn[1],1),1):1;
				mp[tr[P].r]=tr[P].sn[1];
//				updt(tr[P].sn[1]);
			}
			tr[P].l=tr[P].r=X;mp[X]=P;
			updt(P);
			return P;
		}
		inline int fndMn(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[0]; 
			}
			return FP;
		}
		inline int fndMx(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[1];
			}
			return FP;
		}
		inline void cut(int X){
			int D=fndD(X);
			tr[tr[X].fa].sn[D]=0,tr[X].fa=0;
		}
		inline void cnnct(int X,int Y,int D){
			tr[Y].sn[D]=X,tr[X].fa=Y;
			updt(Y);
		}
		inline void prnt(int X,int dep=0){
			if(!X){return;}
			for(int i=1;i<=dep;++i){
				printf(" ");
			}debug(X);
			prnt(tr[X].sn[0],dep+1);
			prnt(tr[X].sn[1],dep+1);
		}
	public:
		inline int CHANGE(int X,int Y){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			tr[P].l=tr[P].r=Y;
			mp[Y]=P;
			splayRnw(P);
			return tr[tr[P].sn[0]].sz+1;
		}
		inline int LST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!L){
				return RT;
			}
			R?(R=fndMn(R),cut(L),cnnct(L,R,0),splayRnw(L)):(cut(L),cnnct(L,P,1));//此处P写成X,调了我一年。 
			return RT;
		}
		inline int RST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!R){
				return RT;
			}
			L?(L=fndMx(L),cut(R),cnnct(R,L,1),splayRnw(R)):(cut(R),cnnct(R,P,0));
			return RT;
		}
		inline int ARNK(int X){
			return fnd(X);
		} 
		//初始化。 
		inline void INIT(int N){
			cnt=1;
			rt=1;
			tr[1].set(1,N,0);
			mp[N]=1;
		}
};
/*
Error:
192600404: 指定的节点不存在。
192600500: 切割的节点不是区间节点。 
*/

int n,m;
Splay T;
void init(){
	int code=0;
	scanf("%d%d",&n,&m);
	T.INIT(n);
	int op,x,y;
	for(int i=1;i<=m;++i){
		scanf("%d",&op);
		switch(op){
			case 1:{
				scanf("%d%d",&x,&y);
				x-=code,y-=code;
				printf("%d\n",code=T.CHANGE(x,y));
//				if(code==95204&&i>=80000){
//					puts("fk1");
//					printf("%d\n",x);
//					return;
//				}
				break;
			}
			case 2:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.LST(x));
				break;
			}
			case 3:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.RST(x));
				break;
			}
			case 4:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.ARNK(x));
				break;
			}
		}
//		printf("CORESIZE:%d\n",T.tr[54567].sz);
	}
}

int main(){
//	freopen("input1.in","r",stdin);
//	freopen("output1.out","w",stdout);
	init();
	return 0;
} 

发表评论

电子邮件地址不会被公开。