记录编号	468703	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]维护数列	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	4.604 s
提交时间	2017-11-01 21:00:56	内存使用	0.31 MiB

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
struct Treap{
	Treap *lc,*rc;
	int size,val,sum,ls,rs,ms,ran,same,rev,Max;
	Treap(int v);
	void up(){
		size=lc->size+1+rc->size;
		sum=lc->sum+val+rc->sum;
		ls=max(lc->ls,lc->sum+val+rc->ls);
		rs=max(lc->rs+val+rc->sum,rc->rs);
		ms=max(max(lc->ms,rc->ms),lc->rs+val+rc->ls);
		Max=max(val,max(lc->Max,rc->Max));
	}
	void flip(){rev^=1;swap(ls,rs);swap(lc,rc);}
	void msame(int tag){
		same=Max=val=tag;
		ls=rs=ms=max(0,sum=tag*size);
	}
	void down();
	~Treap();
}*root,*nil;
Treap::Treap(int v){
	size=1;lc=rc=nil;
	val=sum=Max=v;
	ls=rs=ms=max(v,0);
	ran=rand();
	same=1e9;
	rev=0;
}
Treap::~Treap(){
	if (lc!=nil) delete lc;
	if (rc!=nil) delete rc;
}
void Treap::down(){
	if (same<1e9){
		if (lc!=nil) lc->msame(same);
		if (rc!=nil) rc->msame(same);
		same=1e9;
	}
	if (rev){
		if (lc!=nil) lc->flip();
		if (rc!=nil) rc->flip();
		rev=0;
	}
}
void init(){
	srand(time(0));
	nil=new Treap(0);
	root=nil->lc=nil->rc=nil;
	nil->size=0;
	nil->Max=-1e9;
}
Treap *merge(Treap *x,Treap *y){
	if (x==nil) return y;
	if (y==nil) return x;
	x->down();y->down();
	if (x->ran>y->ran){
		x->rc=merge(x->rc,y);
		x->up();
		return x;
	}
	else{
		y->lc=merge(x,y->lc);
		y->up();
		return y;
	}
}
void split(Treap *x,Treap *&lt,Treap *&rt,int k){
	if (x==nil) return void(lt=rt=nil);
	x->down();
	int i=x->lc->size+1;
	if (k<i){
		split(x->lc,lt,rt,k);
		x->lc=rt;
		(rt=x)->up();
	}
	else{
		split(x->rc,lt,rt,k-i);
		x->rc=lt;
		(lt=x)->up();
	}
}
void split(Treap *&lt,Treap *&mt,Treap *&rt,int p,int len){
	split(root,lt,mt,p-1);
	split(mt,mt,rt,len);
}
int read(){
	int x=0;bool sign=0;char ch=getchar();
	while (ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
	if (ch=='-') sign=1,ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return sign?-x:x;
}
int n,m;
int main()
{
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout);
	init();
	n=read();m=read();
	for (int i=1;i<=n;i++) root=merge(root,new Treap(read()));
	char str[20]="";
	for (int i=1;i<=m;i++){
		scanf("%s",str);
		Treap *lt,*mt,*rt;
		if (str[0]=='I'){
			split(root,lt,rt,read());
			int cnt=read();
			while (cnt--) lt=merge(lt,new Treap(read()));
			root=merge(lt,rt);
		}else
		if (str[0]=='D'){
			int p=read(),len=read();
			split(lt,mt,rt,p,len);
			if (mt!=nil) delete mt;
			root=merge(lt,rt);
		}else
		if (str[0]=='R'){
			int p=read(),len=read();
			split(lt,mt,rt,p,len);
			mt->flip();
			root=merge(lt,merge(mt,rt));
		}else
		if (str[0]=='G'){
			int p=read(),len=read();
			split(lt,mt,rt,p,len);
			printf("%d\n",mt->sum);
			root=merge(lt,merge(mt,rt));
		}else
		if (str[2]=='K'){
			int p=read(),len=read();
			split(lt,mt,rt,p,len);
			mt->msame(read());
			root=merge(lt,merge(mt,rt));
		}
		else printf("%d\n",root->Max>0?root->ms:root->Max);
	}
	return 0;
}