P2042

本地输出：

-231 2021 1215 2077 414 3591 884

答案：

-231 2021 1215 2077 414 3591 884

洛谷上：

259 2021 1705 1681 414 2453 -23

#include<bits/stdc++.h>
#define R register int
using namespace std;
const int N=500005,inf=1e5;
int n,m,rt,tot;
char in[10];
struct node
{
	long long ls,rs,ms,s;
	int fa,ch[2];
	long long va;
	int pt,rv,sz;
	/*void print(int nw,int d)
	{
		cout<<setw(4)<<va;
		for(R i=0;i<=d;i++)  cout<<"   ";
		cout<<"id="<<nw;
		cout<<"  sz="<<sz<<" va="<<va;
		cout<<"  lc="<<ch[0]<<" rc="<<ch[1]<<endl;
		for(R i=0;i<=d;i++)  cout<<"   ";
		cout<<"    pt="<<pt<<" rv="<<rv;
		cout<<"  ls="<<ls<<" rs="<<rs<<" ms="<<ms<<" sum="<<s<<endl;
	}*/
}t[N*8];
int read()
{
	int s=0,w=1;char c=getchar();
	while(!isdigit(c))  w=c=='-'?-1:w,c=getchar();
	while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s*w;
}
void up(int nw)
{
	int l=t[nw].ch[0],r=t[nw].ch[1];
	t[nw].sz=t[l].sz+1+t[r].sz;
	t[nw].s=t[l].s+t[r].s+t[nw].va;
	if(l&&r)
	{
		t[nw].ls=max(t[l].ls,t[l].s+t[nw].va+t[r].ls);
		t[nw].rs=max(t[l].rs+t[nw].va+t[r].s,t[r].rs);
		t[nw].ms=max(max(t[l].ms,t[r].ms),t[l].rs+t[nw].va+t[r].ls);
		return;
	}
	if(!l&&r)
	{
		t[nw].ls=max(t[nw].va,t[nw].va+t[r].ls);
		t[nw].rs=max(t[nw].va+t[r].s,t[r].rs);
		t[nw].ms=max(t[r].ms,t[nw].ls);return;
	}
	if(!r&&l)
	{
		t[nw].ls=max(t[l].ls,t[l].s+t[nw].va);
		t[nw].rs=max(t[nw].va,t[nw].va+t[l].rs);
		t[nw].ms=max(t[l].ms,t[nw].rs);return;
	}t[nw].ls=t[nw].rs=t[nw].ms=t[nw].va;return;
}

void rev(int nw)
{
	if(t[nw].pt!=-inf)  return;
	swap(t[nw].ch[0],t[nw].ch[1]);
	swap(t[nw].ls,t[nw].rs);
	t[nw].rv^=1;
}
void change(int nw,int v)
{
	t[nw].va=t[nw].pt=v;t[nw].rv=0;t[nw].s=1ll*v*t[nw].sz;
	t[nw].ls=t[nw].rs=t[nw].ms=v<0?v:1ll*v*t[nw].sz;
}
void down(int nw)
{
	int l=t[nw].ch[0],r=t[nw].ch[1];
	if(t[nw].rv)  rev(l),rev(r),t[nw].rv=0/*,cout<<"    1   dddddddddddd"<<nw<<'\n'*/;
	if(t[nw].pt!=-inf)  /*cout<<"    2   dddddddddddd"<<nw<<' '<<t[nw].pt<<'\n',*/change(l,t[nw].pt),change(r,t[nw].pt),t[nw].pt=-inf;
}
void rotate(int x)
{
	int f=t[x].fa,ff=t[f].fa,k=t[f].ch[1]==x;
	t[x].fa=ff;t[ff].ch[t[ff].ch[1]==f]=x;
	t[f].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].fa=f;
	t[f].fa=x;t[x].ch[k^1]=f;up(f);up(x);
}
void splay(int x,int y)
{
	int f=t[x].fa,ff=t[f].fa;
	while(f!=y)
	{
		down(f);down(x);
		if(ff!=y)
			if((t[f].ch[1]==x)^(t[ff].ch[1]==f))  rotate(x);
			else  rotate(f);
		rotate(x);f=t[x].fa,ff=t[f].fa;
	}rt=y?rt:x;
}
int kth(int k)
{
	int nw=rt;
	while(1)
	{
		down(nw);
		if(k==t[t[nw].ch[0]].sz+1)  return nw;
		if(k<=t[t[nw].ch[0]].sz)  nw=t[nw].ch[0];
		else  k-=t[t[nw].ch[0]].sz+1,nw=t[nw].ch[1];
	}
}
/*void out(int nw,int d)
{
	down(nw);
	if(t[nw].ch[0])  out(t[nw].ch[0],d+1);
	t[nw].print(nw,d);
	if(t[nw].ch[1])  out(t[nw].ch[1],d+1);
}*/
int main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	n=read();m=read();t[rt=++tot].sz=1;t[tot].pt=-inf;
	t[++tot].fa=tot-1;t[tot-1].ch[1]=tot;
	t[tot].sz=1;t[tot].pt=-inf;
	for(R i=1,a;i<=n;i++)
	{
		t[++tot].va=t[tot].s=t[tot].ls=t[tot].rs=t[tot].ms=read();
		t[tot].fa=tot-1;t[tot-1].ch[1]=tot;
		t[tot].sz=1;t[tot].pt=-inf;
	}
	t[++tot].fa=tot-1;t[tot-1].ch[1]=tot;
	t[tot].sz=1;t[tot].pt=-inf;
	up(tot-1);splay(tot,0);
	//out(rt,0);
	for(R i=1;i<=m;i++)
	{
		//cout<<"     work:"<<i<<endl;
		scanf(" %s",in);
		if(in[0]=='M'&&in[2]=='X')  {printf("%lld\n",t[rt].ms);continue;}
		if(in[0]=='I')
		{
			int l=read(),cnt=read(),r,lst;
			lst=r=kth(l+3);l=kth(l+2);
			splay(l,0);splay(r,l);
			while(cnt--)
			{
				t[lst].ch[lst!=r]=++tot;t[tot].fa=lst;
				lst=tot;t[tot].pt=-inf;
				t[tot].ls=t[tot].rs=t[tot].ms=t[tot].va=read();
			}
			up(lst);splay(tot,0);
			/*cout<<"get="<<l<<' '<<r<<endl;
			out(rt,0),cout<<"\n";*/
			continue;
		}
		int l=read(),r=l+read()-1,v;
		l=kth(l+1),r=kth(r+3);
		splay(l,0);splay(r,l);
		if(in[0]=='D')  t[r].ch[0]=0,up(r),splay(r,0);
		if(in[0]=='M')  change(t[r].ch[0],read()),up(r),splay(t[r].ch[0],0);
		if(in[0]=='R')
		{
			int nw=t[r].ch[0];
			if(t[nw].pt==-inf)  rev(nw),up(r),splay(nw,0);
		}
		if(in[0]=='G')  printf("%lld\n",t[t[r].ch[0]].s);
		/*cout<<"get="<<l<<' '<<r<<endl;
		out(rt,0),cout<<"\n";*/
	}
	return 0;
}