记录编号	372241	评测结果	MMMMMMMMMM
题目名称	[NOI 2005]维护数列	最终得分	0
用户昵称	再见	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-02-17 21:54:18	内存使用	0.00 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
const int MAXN=4000010;
const int INF=500000000;

inline int read(){
	int x=0,f=0;char ch;
	while(ch=getchar(),!isdigit(ch)) ch=='-'?f=1:false;
	while(x=x*10+ch-'0',ch=getchar(),isdigit(ch));
	return f?-x:x;
}

int cnt,n,m,root,size[MAXN],val[MAXN],fa[MAXN],ch[MAXN][2],lm[MAXN],rm[MAXN],mx[MAXN],setv[MAXN],rev[MAXN],sum[MAXN];
char str[20];

inline int max(int a,int b){return a>b?a:b;}

inline void same(int x,int v){
	if(!x) return;
	val[x]=v; sum[x]=size[x]*v; 
	lm[x]=rm[x]=mx[x]=v>0?size[x]*v:v;
}

inline void rever(int x){
	if(!x) return;
	int &lc=ch[x][0],&rc=ch[x][1],t;
	t=lm[x]; lm[x]=rm[x]; rm[x]=t;
	t=lc; lc=rc; rc=t;
}

inline void pushdown(int x){
	if(setv[x]!=1001){
		int &lc=ch[x][0],&rc=ch[x][1];
		setv[lc]=setv[rc]=setv[x];
		same(lc,setv[x]); same(rc,setv[x]);
		setv[x]=1001;
	}
	if(rev[x]){
		int &lc=ch[x][0],&rc=ch[x][1];
		rev[lc]^=1; rev[rc]^=1;
		rever(lc); rever(rc);
		rev[x]=0;
	}
}

inline void update(int x){
	int &lc=ch[x][0],&rc=ch[x][1];
	sum[x]=val[x]+sum[lc]+sum[rc];
	lm[x]=max(lm[lc],sum[lc]+val[x]+max(0,lm[rc]));
	rm[x]=max(rm[rc],sum[rc]+val[x]+max(0,rm[lc]));
	mx[x]=max(max(mx[lc],mx[rc]),val[x]+max(0,lm[rc])+max(0,rm[lc]));
	size[x]=size[lc]+size[rc]+1;
}

inline void rot(int x){
	int y=fa[x],z=fa[y],f=ch[y][0]==x,rc=ch[x][f];
	ch[x][f]=y; ch[y][!f]=rc;
	fa[x]=z; fa[y]=x; fa[rc]=y;
	y==root?root=x:false;
	ch[z][ch[z][1]==y]=x;
	update(y);
}

inline void splay(int x,int anc){
	pushdown(x);
	int reach=x==anc,y;
	while(!reach){
		y=fa[x];
		if(y==anc) reach=true,rot(x);
		else{
			fa[y]==anc?reach=true:false;
			rot((ch[fa[y]][0]==y)==(ch[y][0]==x)?y:x); rot(x);
		}
	}
	update(x);
}

inline void select(int y,int k){
	int x=y;
	while(true){
		pushdown(x);
		if(size[ch[x][0]]+1==k){
			splay(x,y);
			return;
		}
		if(size[ch[x][0]]>=k) x=ch[x][0];
		else k-=size[ch[x][0]]+1,x=ch[x][1];
	}
}

inline void init(){
	cnt=2; root=1;
	ch[1][1]=2; fa[2]=1;
	size[1]=2; size[2]=1;
	mx[0]=lm[0]=rm[0]=-INF;
}

inline void insert(int a,int len){
	select(root,a); select(ch[root][1],1);
	int t=++cnt,p=t,q=t; val[t]=read(); size[t]=1;
	for(int i=2;i<=len;i++)
		t=++cnt,ch[p][1]=t,fa[t]=p,p=t,size[t]=1,val[t]=read();
	ch[ch[root][1]][0]=q; fa[q]=ch[root][1];
	splay(p,root);
}

inline void del(int a,int len){
	select(root,a); select(ch[root][1],len+1);
	int rc=ch[root][1];
	ch[rc][0]=0;
	splay(rc,root);
}

inline void makesame(int a,int len,int v){
	select(root,a); select(ch[root][1],len+1);
	int rc=ch[ch[root][1]][0];
	setv[rc]=v; same(rc,v);
	splay(rc,root);
}

inline void reverse(int a,int len){
	select(root,a); select(ch[root][1],len+1);
	int rc=ch[ch[root][1]][0];
	rev[rc]^=1; rever(rc);
	splay(rc,root);
}

inline int getsum(int a,int len){
	select(root,a); select(ch[root][1],len+1);
	return sum[ch[ch[root][1]][0]];
}

inline int maxsum(){
	select(root,1); select(ch[root][1],size[ch[root][1]]);
	return mx[ch[ch[root][1]][0]];
}

int main(){
	freopen("seq2005.in","r",stdin);
	freopen("seq2005.out","w",stdout);
	for(int i=1;i<MAXN;i++) setv[i]=1001;
	n=read(); m=read();
	init();insert(1,n);
	for(int i=1;i<=m;i++){
		scanf("%s",str); int a,b,c;
		if(str[0]=='G') a=read(),b=read(),printf("%d\n",getsum(a,b));
		if(str[0]=='R') a=read(),b=read(),reverse(a,b);
		if(str[0]=='D') a=read(),b=read(),del(a,b);
		if(str[0]=='I') a=read(),b=read(),insert(a+1,b);
		if(str[2]=='X') printf("%d\n",maxsum());
		if(str[2]=='K') a=read(),b=read(),c=read(),makesame(a,b,c);
	}
	return 0;
}