输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThorn#define inf 0x3f3f3f3fusing namespace std;const int maxn=1000000+5;int tail,stk[maxn];int n,m,now,tot,root,w[maxn],no[maxn],ls[maxn],rs[maxn],fa[maxn],siz[maxn],sum[maxn],rev[maxn],lmax[maxn],rmax[maxn],mmax[maxn],lazy[maxn];char opt[13];inline void reverse(int x){	if(x==0)		return;	swap(ls[x],rs[x]);	swap(lmax[x],rmax[x]);}inline void make_same(int x,int y){	if(x==0)		return;	w[x]=y;sum[x]=siz[x]*y;	lmax[x]=rmax[x]=mmax[x]=max(y,sum[x]);//bu neng wei kong}inline void push_down(int x){	if(x==0)		return;	if(rev[x])		reverse(ls[x]),reverse(rs[x]),rev[ls[x]]^=1,rev[rs[x]]^=1,rev[x]=0;	if(lazy[x]!=-inf)		make_same(ls[x],lazy[x]),make_same(rs[x],lazy[x]),lazy[ls[x]]=lazy[rs[x]]=lazy[x],lazy[x]=-inf;}inline void update(int x){	if(x==0)		return;	lmax[x]=max(lmax[ls[x]],sum[ls[x]]+w[x]+max(0,lmax[rs[x]]));	rmax[x]=max(rmax[rs[x]],sum[rs[x]]+w[x]+max(0,rmax[ls[x]]));	mmax[x]=max(max(mmax[ls[x]],mmax[rs[x]]),w[x]+max(0,rmax[ls[x]])+max(0,lmax[rs[x]]));	sum [x]=sum[ls[x]]+sum[rs[x]]+w[x];	siz [x]=siz[ls[x]]+siz[rs[x]]+1;}inline void zig(int x){ 	int y=fa[x];	update(x);update(y);	if(rs[x])		ls[y]=rs[x],fa[rs[x]]=y;	else		ls[y]=0;	fa[x]=fa[y];	if(fa[x]){		if(ls[fa[y]]==y)			ls[fa[y]]=x;		else				rs[fa[y]]=x;	}	fa[y]=x,rs[x]=y;	update(y),update(x);}inline void zag(int x){	int y=fa[x];	update(x);update(y);	if(ls[x])		rs[y]=ls[x],fa[ls[x]]=y;	else		rs[y]=0;	fa[x]=fa[y];	if(fa[x]){		if(ls[fa[y]]==y)			ls[fa[y]]=x;		else			rs[fa[y]]=x;	}	fa[y]=x,ls[x]=y;	update(y),update(x);}inline void relax(int x,int y){	if(x!=y)		relax(fa[x],y);	push_down(x);}inline void splay(int x,int z){	relax(x,z);	while(fa[x]!=z){		int y=fa[x];		if(fa[y]==z){			if(ls[y]==x)				zig(x);			else				zag(x);		}		else{			if(ls[fa[y]]==y){				if(ls[y]==x)					zig(y),zig(x);				else					zag(x),zig(x);			}			else{				if(rs[y]==x)					zag(y),zag(x);				else					zig(x),zag(x);			}		}	}	update(x);	if(!z)		root=x;	else		update(z);}inline int get_num(void){	if(tail)		return stk[tail--];	return ++tot;}inline int assign(int x){	int tmp=get_num();	rev[tmp]=0;	w[tmp]=no[x];	lazy[tmp]=-inf;	lmax[tmp]=rmax[tmp]=mmax[tmp]=-inf;	return tmp;}inline int build(int l,int r){	if(l==r){		int tmp=assign(l);		update(tmp);return tmp;	}	int mid=(l+r)>>1,L=0,R=0,tmp=assign(mid);	if(l<mid)		L=build(l,mid-1);	if(r>mid)		R=build(mid+1,r);	if(L)		ls[tmp]=L,fa[L]=tmp;	if(R)		rs[tmp]=R,fa[R]=tmp;	update(tmp);	return tmp;}inline void del(int x){	if(x==0)		return;	stk[++tail]=x;	fa[x]=rev[x]=0;lazy[x]=-inf;	lmax[x]=rmax[x]=mmax[x]=-inf;	if(ls[x])		del(ls[x]);	if(rs[x])		del(rs[x]);	ls[x]=rs[x]=0;}inline int find(int rt,int x){	push_down(rt);	if(siz[ls[rt]]+1==x)		return rt;	else if(siz[ls[rt]]+1>x)		return find(ls[rt],x);	else		return find(rs[rt],x-siz[ls[rt]]-1);}inline int read(void){	char ch=getchar();int x=0,f=1;	while(!(ch>=‘0‘&&ch<=‘9‘)){		if(ch==‘-‘)			f=-1;		ch=getchar();	}	while(ch>=‘0‘&&ch<=‘9‘)		x=x*10+ch-‘0‘,ch=getchar();	return f*x;}signed main(void){	memset(ls,0,sizeof(ls));	memset(rs,0,sizeof(rs));	memset(fa,0,sizeof(fa));	memset(rev,0,sizeof(rev));	memset(sum,0,sizeof(sum));	memset(siz,0,sizeof(siz));	memset(lmax,-inf,sizeof(lmax));	memset(rmax,-inf,sizeof(rmax));	memset(mmax,-inf,sizeof(mmax));	memset(lazy,-inf,sizeof(lazy));	tot=tail=0;	n=read(),m=read();now=n;	for(int i=1;i<=n;i++)		no[i]=read();	root=build(1,n);int pos,tot,x;	while(m--){		scanf("%s",opt);		if(opt[0]==‘I‘){			pos=read(),tot=read();			for(int i=1;i<=tot;i++)				no[i]=read();			int tmproot=build(1,tot);			if(now==0)				root=tmproot;			else if(pos==0)				splay(find(root,pos+1),0),ls[root]=tmproot,fa[tmproot]=root,update(root);			else if(pos==now)				splay(find(root,pos),0),rs[root]=tmproot,fa[tmproot]=root,update(root);			else				splay(find(root,pos+1),0),splay(find(root,pos),root),rs[ls[root]]=tmproot,fa[tmproot]=ls[root],update(ls[root]),update(root);			now+=tot;		}		else if(opt[0]==‘D‘){			pos=read(),tot=read();			if(pos==1&&pos+tot-1==now)				root=0;			else if(pos==1)				splay(find(root,pos+tot),0),del(ls[root]),ls[root]=0,update(root);			else if(pos+tot-1==now)				splay(find(root,pos-1),0),del(rs[root]),rs[root]=0,update(root);			else				splay(find(root,pos+tot),0),splay(find(root,pos-1),root),del(rs[ls[root]]),rs[ls[root]]=0,update(ls[root]),update(root);			now-=tot;		}		else if(opt[0]==‘M‘&&opt[2]==‘K‘){			pos=read(),tot=read(),x=read();			if(pos==1&&pos+tot-1==now)				make_same(root,x),lazy[root]=x;			else if(pos==1)				splay(find(root,pos+tot),0),make_same(ls[root],x),lazy[ls[root]]=x;			else if(pos+tot-1==now)				splay(find(root,pos-1),0),make_same(rs[root],x),lazy[rs[root]]=x;			else				splay(find(root,pos+tot),0),splay(find(root,pos-1),root),make_same(rs[ls[root]],x),lazy[rs[ls[root]]]=x;		}		else if(opt[0]==‘R‘){			pos=read(),tot=read();			if(pos==1&&pos+tot-1==now)				reverse(root),rev[root]^=1;			else if(pos==1)				splay(find(root,pos+tot),0),reverse(ls[root]),rev[ls[root]]^=1;			else if(pos+tot-1==now)				splay(find(root,pos-1),0),reverse(rs[root]),rev[rs[root]]^=1;			else				splay(find(root,pos+tot),0),splay(find(root,pos-1),root),reverse(rs[ls[root]]),rev[rs[ls[root]]]^=1;		}		else if(opt[0]==‘G‘){			pos=read(),tot=read();			if(tot==0)				puts("0");			else if(pos==1&&pos+tot-1==now)				splay(find(root,now),0),splay(find(root,1),0),printf("%d\n",sum[root]);			else if(pos==1)				splay(find(root,pos+tot),0),printf("%d\n",sum[ls[root]]);			else if(pos+tot-1==now)				splay(find(root,pos-1),0),printf("%d\n",sum[rs[root]]);			else				splay(find(root,pos+tot),0),splay(find(root,pos-1),root),printf("%d\n",sum[rs[ls[root]]]);		}		else			splay(find(root,now),0),splay(find(root,1),0),printf("%d\n",mmax[root]); 		splay(find(root,1),0);splay(find(root,now),0);	}	return 0;}//Cap ou pas cap. Cap.