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;
} 

lp1110 ZJOI2007 报表统计

事实上对于第一类询问和第二类询问我们可以分别处理。
第二类询问的处理方法是非常显然的。由于只有插入而没有删除操作,因此,第二类询问的答案只会缩小、不会增大。
故而,我们对整个数列的值维护一个Splay,每一次插入一个新的数以后,用它和它的前驱与它和它的后继的差的绝对值来更新第二类的答案。
这可以用multiset来简易地实现。
对于第一类询问,我们发现,维护这个值其实并不是难点——用线段树或者平衡树都可以轻松实现。问题在于,如何在插入新的数之后保持这个值。
我们仔细思考,发现,对于任意一段区间来说,它对答案的贡献只有三个:这个区间的答案,这个区间的左端点和这个区间的右端点。
故而,我们建一棵线段树或者平衡树,维护这三个信息(个人认为线段树比较科学。)每一次修改则修改对应的节点,然后递归向上更新即可。
这样就做完了,个人觉得实现难度还是比较低的。

#include<iostream>
#include<cstdio>
#include<set>
#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
inline int Abs(int X){
	return X>0?X:-X;
}

inline int Min(int A,int B){
	return A<B?A:B;
}

std::multiset<int> st;
int ansS=0x3f3f3f3f;
int n,m,a[500005];

class SegmentTree{
	private:
		class Node{
			public:
				int l;
				int r;
				int dlt;
			inline Node(){
				dlt=0x3f3f3f3f;
			}
			inline void init(int V){
				l=r=V;
			}
			inline void psh(int V){
				dlt=Min(dlt,Abs(r-V));
				r=V;
			}
		};
		Node tr[1100000];
		inline void updt(int X){
			tr[X].l=tr[LS].l;
			tr[X].r=tr[RS].r;
			tr[X].dlt=Min(Min(tr[LS].dlt,tr[RS].dlt),Abs(tr[LS].r-tr[RS].l));
		}
		inline void build(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].init(a[L]);
				return;
			}
			build(L,MID,LS),build(MID+1,R,RS);
			updt(X);
		}
		inline void push(int L,int R,int X,int A,int V){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].psh(V);
				return;
			}
			A>MID?push(MID+1,R,RS,A,V):push(L,MID,LS,A,V);
			updt(X);
		}
		inline void prnt(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				printf("%d:[%d,%d,%d] ",X,tr[X].l,tr[X].r,tr[X].dlt);
				return;
			}
			prnt(L,MID,LS),prnt(MID+1,R,RS);
		}
	public:
		inline void PUSH(int X,int K){
			push(1,n,1,X,K);
		}
		inline void BUILD(){
			build(1,n,1);
		}
		inline int QUERYG(){
			return tr[1].dlt;
		}
		inline void PRINT(){
			prnt(1,n,1);
			puts("");
		}
};

inline void STPUSH(int K){
	st.insert(K);
	std::multiset<int> ::iterator it=st.find(K);
	int ans1,ans2;
	++it;
	if(it!=st.end()){
		ans1=*it;
	}else{
		ans1=0x3f3f3f3f;
	}
	--it;
	if(it!=st.begin()){
		--it;
		ans2=*it;
	}else{
		ans2=0x3f3f3f3f;
	}
	ans1=Abs(K-ans1),ans2=Abs(K-ans2);
	ansS=Min(ansS,Min(ans1,ans2));
}

SegmentTree T;
void init(){
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		STPUSH(a[i]);
	}
	T.BUILD();
	char op[10];
	int k;
	for(int i=1;i<=m;++i){
		std::cin>>op;
		switch(op[4]){
			case 'R':{
				scanf("%d%d",&x,&k);
				T.PUSH(x,k);
				STPUSH(k);
				break;
			}
			case 'G':{
				printf("%d\n",T.QUERYG());
				break;
			}
			case 'S':{
				printf("%d\n",ansS);
				break;
			}
			case 'P':{
				T.PRINT();
				break;
			}
		}
	}
}

int main(){
	init();
	return 0;
}

lp2596 ZJOI2006 书架


看到这一题我们就可以想到Splay。
具体来说,这一题要求维护下列四个操作:
将序列中的一个数与它的前一个数/后一个数交换。
将序列中的一个数移到序列头/序列尾。
如果单单如此的话那这一题就太简单了。对于一二操作只需要直接和前驱、后继调换,对于三四操作只需要将左/右子树移动到右/左子树的最左/右节点的左/右孩子。
但事实上并非这样。这一题对序列中数的操作并非是直接给出的,而是对序列中的每一个点编了号,然后每一次访问这个编号。
但仔细思考就会发现,考虑到对序列的操作只会更换位置,
故而,对于这种操作,我们定义一个数组名为loc,储存的是,编号为\(loc_i\)的数在数列中的标号。
要十分注意编号和逆编号的对应关系。以及交换之后对它们原来的关系的影响。

#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int loc[80005],aloc[80005];
class Splay{
	private:
		class Node{
			public:
				int fa;
				int sn[2];
				int sz;
				inline void prnt(){
					printf("(%d,%d,%d)\n",fa,sn[0],sn[1]);
				}
			inline Node(int FA=0,int LS=0,int RS=0,int SZ=0){
				fa=FA,sn[0]=LS,sn[1]=RS,sz=SZ;
			}
		};
		Node tr[80005];
		int rt;
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
		}
		inline int fndD(int X){
			return tr[tr[X].fa].sn[1]==X;
		}
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			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].fa].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){
			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 int fnd(int K){
			int P=rt,FP=0;
			while(P){
				FP=P;
				if(tr[tr[P].sn[0]].sz+1<K){
					K-=(tr[tr[P].sn[0]].sz+1);
					P=tr[P].sn[1];
				}else if(tr[tr[P].sn[0]].sz<K){
					return P;
				}else{
					P=tr[P].sn[0];
				}
			}
			return FP;
		}
		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 int build(int L,int R,int FA){
			if(L>R){
				return 0;
			}
			tr[MID].fa=FA,tr[MID].sz=1;
			tr[MID].sn[0]=build(L,MID-1,MID);
			tr[MID].sn[1]=build(MID+1,R,MID);
			updt(MID);
			return MID;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].sn[0]);
			printf("%d ",X);
			prnt(tr[X].sn[1]);
		}
	public:
		inline void INIT(int N){
			build(1,N,0);
			rt=(1+N)>>1;
		}
		inline void SWAP(int X,int D){
			splayRnw(X);
			int P=D?fndMn(tr[X].sn[1]):fndMx(tr[X].sn[0]);
			int X_2=aloc[X],P_2=aloc[P];
			std::swap(loc[X_2],loc[P_2]);
			std::swap(aloc[X],aloc[P]);
			splayRnw(X);
		}
		inline void LST(int X){
			splayRnw(X);
			int P=fndMn(tr[X].sn[1]);
			tr[tr[X].sn[0]].fa=P,tr[P].sn[0]=tr[X].sn[0],tr[X].sn[0]=0;
			splayRnw(tr[P].sn[0]);
		}
		inline void RST(int X){
			splayRnw(X);
			int P=fndMx(tr[X].sn[0]);
			tr[tr[X].sn[1]].fa=P,tr[P].sn[1]=tr[X].sn[1],tr[X].sn[1]=0;
			splayRnw(tr[P].sn[1]);
		}
		inline int RNK(int X){
			splayRnw(X);
			return tr[tr[X].sn[0]].sz;
		}
		inline int ARNK(int X){
			int P=fnd(X);
			splayRnw(P);
			return P;
		}
		inline void PRINT(){
			printf("%d ->",rt);
			prnt(rt);
			puts("");
		}
};
int n,m;
Splay T;
void init(){
	scanf("%d%d",&n,&m);
	T.INIT(n);
	int x,t;
	for(int i=1;i<=n;++i){
		scanf("%d",&x);
		loc[x]=i,aloc[i]=x;
	}
	char op[10];
	for(int i=1;i<=m;++i){
		std::cin>>op;
		scanf("%d",&x);
		switch(op[0]){
			case 'T':{
				T.LST(loc[x]);
				break;
			}
			case 'B':{
				T.RST(loc[x]);
				break;
			}
			case 'I':{
				scanf("%d",&t);
				t==0?0:(T.SWAP(loc[x],t==-1?0:1),0);
				break;
			}
			case 'A':{
				printf("%d\n",T.RNK(loc[x]));
				break;
			}
			case 'Q':{
				printf("%d\n",aloc[T.ARNK(x)]);
				break;
			}
		}
	} 
}

int main(){
	init();
	return 0;
}

lp2042 NOI2005 维护数列

Splay裸题。
具体来说,维护两个延迟标记,翻转标记和改变标记。然后对于每一个标记考虑下传。
对于两种询问各自更新区间和与区间最大子段和。
一个区间的最大子段和有可能有三种情况:左子区间的最大子段和,右子区间的最大子段和,以及跨过两个区间的子段和。
故而我们对每个区间关于子段和维护三个信息,左起最大子段和、右起最大子段和以及总最大子段和。
而对于左起最大子段和的更新,则考虑两种情况:左子区间的最大子段和,以及整个左子区间加上根节点再加上右子区间的左起最大子段和。
右起同理。

注意:

  • 1.updt时应当先updt(tr[X].sn[D^1])再updt(X)
  • 2.添加节点和各种修改之后应当科学地rnw
  • 3.添加节点时应当注意是从posi~posi+1之间的区间。
  • 4.一个节点被删除以后,rnw它的父亲是没有意义的,应当从根开始rnw
  • 5.内存回收机制中,添加入栈应当是++tp,出栈应当是tp–
  • 6.考虑updt和pshd的方式:对于每一次pshd,我们应该统一修改它的子节点的标记,并对它的子节点计算贡献,然后取消它本身的标记;打标记的时候对它本身计算好贡献。
  • 换句话说,不要在统计一个节点的贡献之前,updt它的父亲。
  • 7.加入节点应当加入成一棵二叉树,而不是一条链。根据我根本不懂的势能分析法,加入一棵二叉树带来的势能改变是常数乘大小级的,而一条链则是对数乘大小级的。
  • 8.对于MAX-SUM操作,必须要至少选中一个节点,所以应当额外维护一个最大值。

#include<iostream>
#include<cstdio>
#define R register
#define MAGIC 19260817
#define MID ((L+R_R)>>1)
/*

*/
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Chck(int X){
    return X>0?X:0;
}
inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
//表示特殊状态 
class Splay{
    private:
        class Node{
            public:
    			int fa;
    			int sn[2];
    			int sz;
    			int sm;
    			int lmxsm;
    			int rmxsm;
    			int mxsm;
    			int mx;
    			int v;
    			int lzy_flp;
    			int lzy_chng;
    			inline void set(int FA,int V){
    			    fa=FA,sz=1,sm=v=mxsm=mx=V,lmxsm=rmxsm=Chck(V);
    			    sn[0]=sn[1]=lzy_flp=0,lzy_chng=MAGIC;
                }
                inline void init(){
                    fa=sz=sm=lmxsm=rmxsm=v=sn[0]=sn[1]=lzy_flp=0;
                    mxsm=mx=-MAGIC;
                    lzy_chng=MAGIC;
                }
        };
        Node tr[500005];
        int st[500005],tp,cnt,rt;
        inline int fndD(int X){
            return tr[tr[X].fa].sn[0]==X?0:1;
        }
        inline void chng(int X){
            tr[X].sm=tr[X].lzy_chng*tr[X].sz,tr[X].mxsm=Max(tr[X].lzy_chng,tr[X].lzy_chng*tr[X].sz);tr[X].lmxsm=tr[X].rmxsm=Chck(tr[X].lzy_chng*tr[X].sz);
            tr[X].v=tr[X].mx=tr[X].lzy_chng;
        }
        inline void flp(int X){
            Swap(tr[X].sn[0],tr[X].sn[1]);
            Swap(tr[X].lmxsm,tr[X].rmxsm);
        }
        inline void pshd(int X){
            if(!X){
                return;
            }
            if(tr[X].lzy_chng!=MAGIC){
            	tr[tr[X].sn[0]].lzy_chng=tr[tr[X].sn[1]].lzy_chng=tr[X].lzy_chng;
                chng(tr[X].sn[0]),chng(tr[X].sn[1]);
                tr[X].lzy_chng=MAGIC;
            }
            if(tr[X].lzy_flp){
            	tr[tr[X].sn[0]].lzy_flp^=1,tr[tr[X].sn[1]].lzy_flp^=1;
                flp(tr[X].sn[0]),flp(tr[X].sn[1]);
                tr[X].lzy_flp=0;
            }
        }
        inline void updt(int X){
            if(!X){
                return;
            }
            tr[X].sm=tr[tr[X].sn[0]].sm+tr[tr[X].sn[1]].sm+tr[X].v;
            tr[X].mx=Max(Max(tr[tr[X].sn[0]].mx,tr[tr[X].sn[1]].mx),tr[X].v);
            tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+1;
            tr[X].lmxsm=Max(tr[tr[X].sn[0]].sm+tr[X].v+tr[tr[X].sn[1]].lmxsm,tr[tr[X].sn[0]].lmxsm);
            tr[X].rmxsm=Max(tr[tr[X].sn[1]].sm+tr[X].v+tr[tr[X].sn[0]].rmxsm,tr[tr[X].sn[1]].rmxsm);
            tr[X].mxsm=Max(Max(tr[tr[X].sn[0]].mxsm,tr[tr[X].sn[1]].mxsm),tr[tr[X].sn[0]].rmxsm+tr[X].v+tr[tr[X].sn[1]].lmxsm);
        }
        inline void splayOne(int X){
            int D=fndD(X),D2=fndD(tr[X].fa);
            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].fa].fa;
            tr[tr[X].sn[D^1]].fa=X,tr[tr[X].fa].sn[D2]=X;
            updt(tr[X].sn[D^1]),updt(X);
        }
        inline void splayTwo(int 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){
            if(!X){
                return;
            }
            //printf("%d->",X);
            while(tr[X].fa){
                splayTwo(X);
                //printf("[%d,%d,%d[%d,%d](%d)] ",X,tr[X].fa,tr[tr[X].fa].fa,tr[X].sn[0],tr[X].sn[1],fndD(X));
            }
            //puts("");
            rt=X;
        }
        //注意,权值splay中的fnd函数实质上求的是排名为K的节点。 
        inline int fnd(int K){
            R int P=rt,FP=0;
            while(P){
                pshd(P);
                FP=P;
                if(tr[tr[P].sn[0]].sz+1<K){
                    K-=(tr[tr[P].sn[0]].sz+1);
                    P=tr[P].sn[1];
                }else if(tr[tr[P].sn[0]].sz<K){
                    return P;
                }else{
                    P=tr[P].sn[0];
                }
            }
            return FP;
        }
        inline int nwlc(int FA,int D,int V){
            if(!cnt){
                rt=1;
            }
            int P=tp?st[tp--]:++cnt;
            tr[FA].sn[D]=P;
            tr[P].set(FA,V);
            return P;
        }
        inline int preSplay(int L,int LEN){
            int __L__=fnd(L),__R__=fnd(L+LEN+1);
            splayRnw(tr[__L__].fa),splayRnw(tr[__R__].fa);
            splayRnw(__L__);
            splayRnw(__R__);
            //printf("%d,%d,%d\n",rt,tr[rt].sn[0],tr[rt].sn[1]);
            if(tr[__L__].fa!=__R__&&__L__!=__R__){
                splayOne(__L__);
            }
            pshd(tr[tr[rt].sn[0]].sn[1]);
            return tr[rt].sn[0];
        }
        inline void rmv(int X){
            if(!X){
                return;
            }
            rmv(tr[X].sn[0]);
            rmv(tr[X].sn[1]);
            tr[tr[X].fa].sn[fndD(X)]=0;
            tr[tr[X].sn[0]].fa=tr[tr[X].sn[1]].fa=0;
            st[++tp]=X;
        }
        inline void prnt(int X, int dep=0){
            if(!X){
                return;
            }
            //pshd(X);
            prnt(tr[X].sn[0], dep+1);
            //printf("{%d}[%d](%d,%d)[%d][%d,%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].mxsm,tr[X].lmxsm,tr[X].rmxsm);
            for(int i = 1; i <= dep; ++i) printf("口");
        	//printf("ID:%d    VAL:%d    SM:%d   CHANGE_TAG:%d \n",X,tr[X].v,tr[X].sm,tr[X].lzy_chng);
        	printf("%d %d\n",tr[X].v,tr[X].mxsm);
            prnt(tr[X].sn[1], dep+1);
        }
        inline void build(int L,int R_R,int *IN,int D,int FA){
        	if(L>R_R){
        		return;
			}
        	int P=nwlc(FA,D,IN[MID]);
        	build(L,MID-1,IN,0,P);
        	build(MID+1,R_R,IN,1,P);
        	updt(P);
		}
    public:
        inline void INSERT(int L,int TOT,int *IN){
            int X=preSplay(L+1,0);
            build(1,TOT,IN,1,X);
            updt(X),updt(tr[X].fa),updt(tr[tr[X].fa].fa);
       }
        inline void DELETE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            rmv(X);
            updt(tr[rt].sn[0]),updt(rt);
        }
        inline void MAKE_SAME(int L,int LEN,int V){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_chng=V;
            chng(X);
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void REVERSE(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            tr[X].lzy_flp^=1;
            if(tr[X].lzy_flp){
            	flp(X);
            }
            updt(tr[X].fa),updt(tr[tr[X].fa].fa);
        }
        inline void GET_SUM(int L,int LEN){
            int X=tr[preSplay(L,LEN)].sn[1];
            printf("%d\n",tr[X].sm);
        }
        inline void MAX_SUM(){
            printf("%d\n",(tr[rt].mxsm)?tr[rt].mxsm:tr[rt].mx);
        }
        inline void INIT(int N,int *IN){
            tr[0].init();
            rt=tp=cnt=0;
            int X=0;
            for(int i=1;i<=N;++i){
                X=nwlc(X,1,IN[i]);
            }
            nwlc(1,0,-MAGIC),nwlc(X,1,-MAGIC);
            splayRnw(N+1),splayRnw(N+2);
        }
        inline void PRINT(){
            printf("%d ->\n",rt);
            prnt(rt);
            puts("");
        }
};
int n,m;
int a[4000005];
Splay T;
void init(){
    scanf("%d%d",&n,&m);
    int posi,tot,c;
    char op[10];
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
    }
    T.INIT(n,a);
    for(int i=1;i<=m;++i){
        std::cin>>op;
        switch(op[2]){
            case 'S':{
                scanf("%d%d",&posi,&tot);
                for(int j=1;j<=tot;++j){
                    scanf("%d",a+j);
                }
                T.INSERT(posi,tot,a);
                break;
            }
            case 'L':{
                scanf("%d%d",&posi,&tot);
                T.DELETE(posi,tot);
                break;
            }
            case 'K':{
                scanf("%d%d%d",&posi,&tot,&c);
                T.MAKE_SAME(posi,tot,c);
                break;
            }
            case 'V':{
                scanf("%d%d",&posi,&tot);
                T.REVERSE(posi,tot);
                break;
            }
            case 'T':{
                scanf("%d%d",&posi,&tot);
                T.GET_SUM(posi,tot);
                break;
            }
            case 'X':{
                T.MAX_SUM();
                break;
            }
        }
    }
}

int main(){
    init();
    return 0;
}

平衡树-Splay

我们将一棵以\(Splay\)方式维护的二叉搜索树封装为一个对象。
对于这个对象,我们定义它的一类私有对象\(Node\),代表二叉搜索树上的一个节点。
对于这个节点,在通常情况下,我们需要维护的信息包括:
\(sn\),这是一个有两个元素的数组。其中第\(0\)项表示左子节点,第\(1\)表示右子节点。
\(fa\),表示它的父节点。
\(v\),表示它的值。
\(nm\),表示值为\(v\)的数的个数。
\(sz\),表示所有子节点中的数的个数的和。

对于一棵二叉搜索树上的一个节点,我们定义它的旋转、单旋和双旋操作。
定义一个函数\(fndD(X)\),表示一个节点相对于它的父节点是\(fndD(X)\)子节点
那么,一个节点\(X\)的旋转操作为:
将它的\(fndD(X)\ xor\ 1\)子节点作为它的父节点的\(fndD(X)\)子节点,并将\(X\)作为它的祖父节点的\(fndD(X_fa)\)节点,然后将它原来的父节点变成它的\(fndD(X)\ xor \ 1\)节点。
定义一个节点的单旋操作为,将这个节点向上旋转两次。
定义一个节点的双旋操作为,将这个节点的父节点向上旋转一次,然后再将这个节点向上旋转一次。
同时,我们定义一个将一个节点一直依据下述方法单旋/双旋到根的操作为一个伸展操作:
对于一个相对于其父亲的位置与其父亲相对于其祖父的位置相同的节点,对它采用双旋操作。
对于一个相对于其父亲的位置与其父亲相对于其祖父的位置不同的节点,对它采用单旋操作。


下面我们用一种被称为势能分析法的复杂度分析方式来分析它的复杂度。

我们定义关于一个节点\(X\)的势能函数\(\phi(X)\),定义为它的子树大小取对数。我们定义关于整棵二叉搜索树\(T\)的一个势能函数\(\Phi (T)\),定义为它的所有节点的\(\phi\)值之和。

对于第\(i\)次操作,我们定义一个函数\(T\)和一个摊还代价辅助函数\(A\),其中\(T(i)\)表示第\(i\)次操作消耗的实际时间。\(A(i)\)由下述式子定义:
$$A_{i}=T_{i}+\Phi_{i}-\Phi_{i-1}$$
那么,我们可以得到公式:
$$A_{sum}=\sum_{i=1}^{q}A_{i}=\sum_{i=1}^{q}T_{i}+\Phi_{q}-\Phi_{0}$$
故而,我们只需要求出对于每一次操作的\(T\)与\(\Delta\Phi\)即可。

考虑到,每一个操作事实上都可以视为一次\(Splay\)操作,所以我们只需要考虑各类\(Splay\)操作造成的影响即可。
故而,我们需要计算的便是旋转、单旋和双旋对的操作复杂度以及它们对\(\Phi(T)\)的影响。

首先我们分析旋转操作。
容易知道,对于一次关于节点\(X\)的旋转操作,会改变\(\phi\)值的有且仅有两个节点:\(X\)和它的父亲\(Y\)。
我们定义\(X\)旋转后的节点为\(X’\),\(Y\)旋转后的节点为\(Y’\),很容易可以得到一个式子:
$$\Delta\Phi = \phi_{X’} – \phi_{X} + \phi_{Y’} – \phi_{Y}$$
考虑到旋转操作后,\(X’\)位于\(Y\)的位置,并且节点的数量没有增减、对父节点也没有影响,所以得到\(\phi_{X’}=\phi_{Y}\)
考虑\(Y’\)是\(X’\)的子节点,我们可以得到
$$ \phi_{X’} > \phi_{Y’}$$
将上述两式代入式中,可得:
$$\Delta\Phi < \phi_{X’} – \phi_{X}$$
于是可以证明,一次旋转的均摊复杂度上界是\(O(\phi_{X’}-\phi_{X})\)

然后我们分析单旋操作。
依然是定义一个关于节点\(X\)的旋转操作,定义它的父亲为\(Y\),祖父为\(Z\),旋转后分别为\(X’,Y’,Z’\)
很容易可以得到一个式子:
$$\Delta\Phi = \phi_{X’} – \phi_{X} + \phi_{Y’} – \phi_{Y} + \phi_{Z’} – \phi_{Z}$$
同理于旋转操作,我们可以得到:
$$\phi_{X’} = \phi_{Z}$$
故而:
$$\Delta\Phi = – \phi_{X} + \phi_{Y’} – \phi_{Y} + \phi_{Z’}$$
同理于旋转操作,我们可以得到:
$$\phi_{Y’}<\phi_{X’},\phi_{X}<\phi_{Y}$$ 故而:$$\Delta\Phi < \phi_{X’} + \phi_{Z’} – 2\phi_{X}$$$$\Delta\Phi < 2(\phi_{X’}-\phi_{X}) – \phi_{X’} – \phi_{Z’}$$又,$$\phi_{X’} + \phi_{Z’} = log_{2}{|X’||Z’|} > 2$$
所以,
$$\Delta\Phi < 2(\phi_{X’}-\phi_{X}) – 2$$

故而单旋操作的复杂度为\(O(\phi_{X’}-\phi_{X})\)

双旋操作的复杂度同理。

令总共进行了\(n\)次旋转操作,对于总体的复杂度上界,我们有:
$$A_{sum}<\sum_{i=1}^{n}\phi_{i}-\phi_{i-1}$$
故而得到最终的摊还复杂度:\(O(\phi_{n})\)


然而,上述的势能分析法仍然不够直观。下面我们考虑一种基于伸展操作的性质的另一种分析法。
引理一: 每一次伸展操作,必然会使得从这个节点到根的一条链的长度折半。
首先我们考虑单旋和双旋操作的使用情况。
我们称应当使用双旋的情况为一字型,应当使用单旋的情况为之字形,很容易可以发现,原来已有的一条链总是会被拆成两个部分。
而,详细地考虑各种情况,我们发现,不存在一种链,使得这种折半失效。
故而,我们得到了引理一。

下面考虑引理一是怎样在实际情况中发挥作用的。
我们说一个节点的深度可接受,指的是它的深度是\(log_2n\)的常数倍。
考虑对某一个节点进行操作。如果这个节点的深度可接受,那么操作它的复杂度也是可接受的。
如果这个节点的深度不可接受,根据引理一,总是可以在\(log_2n\)次操作以内将其的深度变为可接受的。
而每一次操作最多只会令这个链的深度加一,因此\(log_2n\)次操作的复杂度可以均摊到那些令这个链深度加一的操作上,从而使操作的均摊浮渣度仍然是可接受的。

注意:
1.三目运算符优先级比逗号高。
2.函数名不要搞混。
3.注意区分节点大小和子树大小。
4.当寻找前驱的时候,当前值与当前点的值相等应当向左走;当寻找后继时,当前值与当前点的值相等应当向右走。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXQ 1000005
inline int Max(int A,int B){
    return A>B?A:B;
}
inline int Min(int A,int B){
    return A<B?A:B;
}
class Splay{
	private:
		class Node{
    		public:
    			int sn[2];
    			int fa;
    			int v;
    			int nm;
    			int sz;
    			inline void set(int FA,int LS,int RS,int V){
    			    fa=FA,v=V,sn[0]=LS,sn[1]=RS,nm=1,sz=1;
                }
                inline void init(){
                	sn[0]=sn[1]=fa=v=nm=sz=0;
				}
		};
		int INF;
		Node tr[MAXQ];
		int st[100005],tp,cnt,rt;
		inline int fndD(int X){
			return tr[tr[X].fa].sn[0]==X?0:1;
		}
		inline void szRnw(int X){
		    tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].nm;
        }
		inline void splayOne(int X){
			int D=fndD(X),D2=fndD(tr[X].fa);
			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].sn[D^1]].fa=X;tr[tr[X].fa].sn[D2]=X;
			szRnw(tr[X].sn[D^1]);szRnw(X);
			if(!tr[X].fa){
				rt=X;
			}
		}
		inline void splayTwo(int 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);
            }
		}
		inline int nwlc(int FA,int LS,int RS,int V,int D){
			if(!cnt){
				rt=1;
			}
			int P=tp?st[tp--]:++cnt;
		    tr[FA].sn[D]=P;
		    tr[P].set(FA,LS,RS,V);
		    return P;
        }
        inline int fnd(int V){
            int P=rt,FP=0;
            while(P){
                FP=P;
                if(tr[P].v==V){
                    splayRnw(P);
                    return P;
                }
                P=tr[P].sn[tr[P].v>V?0:1];
            }
            return FP;
        }
        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 clr(int X,int D){
			if(D==2){
				tr[X].init();
				st[++tp]=X;
				return;
			}
			rt=tr[X].sn[D],tr[tr[X].sn[D]].fa=0;
			tr[X].init();
			st[++tp]=X;
		}
		inline void init(int P){
			if(!tr[P].sn[0]||!tr[P].sn[1]){
				tr[P].sn[0]?(clr(P,0)):(tr[P].sn[1]?clr(P,1):clr(P,2));
			}else{
				int RS=fndMn(tr[P].sn[1]);
				tr[RS].sn[0]=tr[P].sn[0],tr[tr[P].sn[0]].fa=RS;
				clr(P,1);
				splayRnw(RS);
			}
			if(!tr[rt].v&&!tr[rt].sz&&!tr[rt].fa&&!tr[rt].nm){
				splayInit();
			}
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].sn[0]);
			printf("(%d)%d:[%d,%d][%d] ",X,tr[X].v,tr[X].sn[0],tr[X].sn[1],tr[X].fa);
			prnt(tr[X].sn[1]);
		}
	public:
	    inline void psh(int V){
	        int P=rt,FP=0,D=0;
	        while(P){
	            FP=P;
	            if(tr[P].v==V){
	                ++tr[P].nm;
	                splayRnw(P);
	                return;
                }
                D=tr[P].v>V?0:1;
	            P=tr[P].sn[tr[P].v>V?0:1];
            }
            splayRnw(nwlc(FP,0,0,V,D));
        }
        inline void del(int V){
            int P=fnd(V);
            splayRnw(P);
            tr[P].nm>1?(--tr[P].nm):(init(P),0);
        }
        inline int fndPre(int V){
            int P=rt,RT=-INF;
            while(P){
                RT=tr[P].v<V?Max(RT,tr[P].v):RT;
                P=tr[P].sn[tr[P].v<V?1:0];
            }
            return RT;
        }
        inline int fndNxt(int V){
            int P=rt,RT=INF;
            while(P){
                RT=tr[P].v>V?Min(RT,tr[P].v):RT;
                P=tr[P].sn[tr[P].v>V?0:1];
            }
            return RT;
        }
        inline int rnk(int V){
            int P=rt,RT=0;
            while(P){
                if(tr[P].v>V){
                    P=tr[P].sn[0];
                }else if(tr[P].v==V){
                    RT+=tr[tr[P].sn[0]].sz;
                    splayRnw(P);
                    return RT+1;
                }else{
                    RT+=tr[tr[P].sn[0]].sz+tr[P].nm;
                    P=tr[P].sn[1]; 
                }
            }
            return RT+1;
        }
        inline int aRnk(int V){
            int P=rt;
            while(P){
                if(tr[tr[P].sn[0]].sz+tr[P].nm<V){
                    V-=(tr[tr[P].sn[0]].sz+tr[P].nm);
                    P=tr[P].sn[1];
                }else if(tr[tr[P].sn[0]].sz<V){
                    return tr[P].v;
                }else{
                    P=tr[P].sn[0];
                }
            }
            return P;
        }
        inline void splayInit(){
			INF=2147483647,tp=0,cnt=0,rt=0;
			memset(tr,0,sizeof(tr));
		}
		inline void splayPrnt(){
			prnt(rt);
			puts("");
		}
}; 
Splay T;
void init(){
	int n,x,op;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		//T.splayPrnt();
		scanf("%d%d",&op,&x);
		switch(op){
			case 1:{
				T.psh(x);
				break;
			}
			case 2:{
				T.del(x);
				break;
			}
			case 3:{
				printf("%d\n",T.rnk(x));
				break;
			}
			case 4:{
				printf("%d\n",T.aRnk(x));
				break;
			}
			case 5:{
				printf("%d\n",T.fndPre(x));
				break;
			}
			case 6:{
				printf("%d\n",T.fndNxt(x));
				break;
			}
		}
	}
}
int main(){
//	freopen("Splay.out","w",stdout);
	T.splayInit();
	init();
	return 0;
}