[NOI2005] 维护数列

link

Splay维护序列的一个较为高级的实例，其它没什么，调得挺顺利的也没什么好说的，除了脑残一下wa#3以外其它都还好。需要告诫后人的是一定要注意摒弃那两个哨兵点，不然会死得很惨。

#include
//#define zczc
const int N=500010;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int op(){
	char w[10];scanf("%s",w);
	switch(w[0]){
		case 'I':return 1;break;//insert
		case 'D':return 2;break;//delete
		case 'M':return w[2]=='K'?3:6;break;//same&max_sum
		case 'R':return 4;break;//reverse
		case 'G':return 5;break;//get_sum
	}
}
inline int min(int s1,int s2){
	return s1r)return 0;int x=kk();int mid=l+r>>1;
	t[x].data=a[mid];t[x].size=1;t[x].f=ff;
	lc=build(l,mid-1,x);rc=build(mid+1,r,x);
	pushup(x);return x;
}
inline void link(int x,int kk,int y){
	t[x].ch[kk]=y;t[y].f=x;return;
}
inline void rotate(int x){
	int y=t[x].f;int z=t[y].f;int kk=x==t[y].ch[1];
	link(z,t[z].ch[1]==y,x);
	link(y,kk,t[x].ch[kk^1]);
	link(x,kk^1,y);pushup(y);pushup(x);return;
}
inline void splay(int x,int rt){
	while(t[x].f^rt){
		int y=t[x].f;int z=t[y].f;
		if(z^rt)(t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);rotate(x);
	}if(rt==0)root=x;
}
inline int find(int val){
	int x=root;
	while(x){
		pushdown(x);
		if(val<=t[lc].size)x=lc;
		else{
			val-=t[lc].size+1;
			if(!val)return x;
			x=rc;
		}
	}
}
inline void dell(int x){
	if(!x)return;dell(lc);dell(rc);del(x);
}
inline void move(int pl,int pr){
	splay(pl,0);splay(pr,pl);return;
}
inline void repush(int pl,int pr){
	pushup(pr);pushup(pl);return;
}
inline void dfs(int x){
	if(!x)return;
	if(x==root)printf("______________\n");
	printf("%d %d %d %d&%d\n",x,t[x].data,t[x].size,lc,rc);dfs(lc);dfs(rc);
	if(x==root)printf("______________\n");
	return;
}
#undef lc
#undef rc

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	
	read(m);read(n);
	for(int i=1;i<=m;i++)read(a[i+1]);
	root=build(1,m+2,root);
	int l,r,num,data,pl,pr;
	while(n--){
		switch(op()){
			case 1:
				read(l);read(num);l++;m+=num;
				for(int i=1;i<=num;i++)read(a[i]);
				move(pl=find(l),pr=find(l+1));
				t[pr].ch[0]=build(1,num,pr);repush(pl,pr);
				break;
			case 2:
				read(l);read(num);m-=num;
				move(pl=find(l),pr=find(l+num+1));
				dell(t[pr].ch[0]);t[pr].ch[0]=0;repush(pl,pr);
				break;
			case 3:
				read(l);read(num);read(data);
				move(pl=find(l),pr=find(l+num+1));
				pushnows(t[pr].ch[0],data);repush(pl,pr);
				break;
			case 4:
				read(l);read(num);
				move(pl=find(l),pr=find(l+num+1));
				pushnowa(t[pr].ch[0]);repush(pl,pr);
				break;
			case 5:
				read(l);read(num);
				move(pl=find(l),pr=find(l+num+1));
				printf("%d\n",t[t[pr].ch[0]].sum);repush(pl,pr);
				break;
			case 6:
				l=1,r=m+2;move(pl=find(l),pr=find(r));
				printf("%d\n",t[t[pr].ch[0]].msum);
				break;
		}
	}
	
	return 0;
}

/*
1 insert
2 delete
3 same
4 reverse
5 get_sum
6 get_max
*/