#include<bits/stdc++.h>
#define LL int
using namespace std;
namespace IO
{
	template <typename T> void read(T &x)
	{
		int pl=1;
		x=0;
		char c=getchar();
		while(!(c>='0'&&c<='9'))
		{
			if(c=='-') pl=-1;
			c=getchar();
		}
		while(c>='0'&&c<='9')
			x=x*10+c-'0',c=getchar();
		x*=pl;
	}
	template <typename T> void print(T x,char c)
	{
		if(x==0)
			putchar('0');
		if(x<0)
			putchar('-'),x=-x;
		int s[21]={0};
		while(x)
		{
			s[++s[0]]=x%10;
			x/=10;
		}
		for(int i=s[0];i>=1;i--)
			putchar(s[i]+'0');
		putchar(c);
	}
}
const int N=5e6+5;
const int inf=2e9;
int n,m,idx,Rt;
struct Splay
{
	int fa,sz,son[2];//Splay树
	int nm,lmx,rmx,sm,mx;//区间信息的维护
	bool ly0;
	int ly1;//懒标记的维护，0表示反转与否，1表示整体修改(不修改为inf) 
}sum[N];
void pushup(int num)
{
	if(num==0) return;
	int lsn=sum[num].son[0],rsn=sum[num].son[1];
	sum[num].sm=sum[lsn].sm+sum[rsn].sm+sum[num].nm;
	sum[num].sz=sum[lsn].sz+sum[rsn].sz+1;
	sum[num].mx=max(sum[num].nm,max(sum[lsn].mx,sum[rsn].mx));
	sum[num].mx=max(sum[num].mx,max(sum[lsn].sm+sum[num].nm,sum[rsn].sm+sum[num].nm));
	sum[num].mx=max(sum[num].mx,sum[lsn].sm+sum[rsn].lmx+sum[num].nm);
	sum[num].mx=max(sum[num].mx,sum[rsn].sm+sum[lsn].rmx+sum[num].nm);
	sum[num].lmx=max(sum[lsn].lmx,sum[lsn].sm+sum[num].nm);
	sum[num].rmx=max(sum[rsn].rmx,sum[rsn].sm+sum[num].nm);
	sum[num].lmx=max(sum[num].lmx,sum[lsn].sm+sum[num].nm+sum[rsn].lmx);
	sum[num].rmx=max(sum[num].rmx,sum[rsn].sm+sum[num].nm+sum[lsn].rmx);
}
void Turn(int num)
{
	if(num==0) return;
	sum[num].ly0^=1;
	swap(sum[num].son[0],sum[num].son[1]);
	swap(sum[num].lmx,sum[num].rmx);
}
void Chge(int num,int pl)
{
	if(num==0) return;
	sum[num].ly1=pl;
	sum[num].nm=pl;
	sum[num].sm=(LL)sum[num].sz*pl;
//	sum[num].mx=pl>0?pl*(LL)sum[num].sz:pl;
//	sum[num].lmx=sum[num].rmx=max(pl,0ll)*(LL)sum[num].sz;
	sum[num].mx=sum[num].lmx=sum[num].rmx=pl>0?pl*(LL)sum[num].sz:pl;
}
void pushdown(int num)
{
	int lsn=sum[num].son[0],rsn=sum[num].son[1];
	if(sum[num].ly0)
		Turn(lsn),Turn(rsn),sum[num].ly0=0;
	if(sum[num].ly1!=inf)
		Chge(lsn,sum[num].ly1),Chge(rsn,sum[num].ly1),sum[num].ly1=inf;
}
void rotate(int x)//单次旋转 
{
	int y=sum[x].fa,z=sum[y].fa,o=(sum[y].son[1]==x);
	if(x==11&&z==2)
		x=11;
	pushdown(z),pushdown(y),pushdown(x);
	sum[y].son[o]=sum[x].son[o^1];
	sum[sum[x].son[o^1]].fa=y;
	sum[x].son[o^1]=y;
	sum[y].fa=x;
	sum[z].son[sum[z].son[1]==y]=x;
	sum[x].fa=z;
	pushup(y),pushup(x),pushup(z);
}
void splay(int x,int f)//旋转x到f
{
	for(int y;y=sum[x].fa,y!=f;rotate(x))
		if(sum[y].fa!=f)
			rotate((sum[sum[y].fa].son[1]==y)==(sum[y].son[1]==x)?y:x);
	if(f==0) Rt=x;
}
void build(int l,int r,int &num,int f)
{
	num=++idx;
	sum[num].lmx=sum[num].rmx=sum[num].mx=-inf;
	sum[num].ly1=inf;
	int mid=(l+r)>>1;
	if(mid-1>=l) build(l,mid-1,sum[num].son[0],num);
	if(mid!=0&&mid!=n+1) IO::read(sum[num].nm);
	else sum[num].nm=0;
	sum[num].fa=f;
	if(mid+1<=r) build(mid+1,r,sum[num].son[1],num);
	pushup(num);
}
int kth(int x)
{
	x++;
	int nw=Rt;
	while(1)
	{
		pushdown(nw);
		int lsz=sum[sum[nw].son[0]].sz;
		if(lsz>=x)
		{
			nw=sum[nw].son[0];
			continue;
		}
		if(lsz+1==x)
		{
			return nw;
		}
		x-=lsz+1;
		nw=sum[nw].son[1];
	}
}
int main()
{
//	freopen("P2042_2.in","r",stdin);
//	freopen("P2042_2.out","w",stdout);
	IO::read(n),IO::read(m);
	sum[0].lmx=sum[0].rmx=sum[0].mx=-inf;
	sum[0].ly1=inf;
	build(0,n+1,Rt,0);
	while(m--)
	{
		char op[15];
		scanf("%s",op);
		if(strcmp(op,"INSERT")==0)
		{
			int x1,x2,y;
			IO::read(x1),IO::read(y);
			x2=x1+1;
			x1=kth(x1),x2=kth(x2);
			splay(x1,0),splay(x2,x1);
			build(1,y,sum[x2].son[0],x2);
		}
		if(strcmp(op,"DELETE")==0)
		{
			int x,y;
			IO::read(x),IO::read(y);
			y=x+y,x--;
			x=kth(x),y=kth(y);
			splay(x,0),splay(y,x);
			sum[y].son[0]=0;
			pushup(y),pushup(x);
		}
		if(strcmp(op,"MAKE-SAME")==0)
		{
			int x,y;
			int z;
			IO::read(x),IO::read(y),IO::read(z);
			y=x+y,x--;
			x=kth(x),y=kth(y);
			splay(x,0),splay(y,x);
			Chge(sum[y].son[0],z);
		}
		if(strcmp(op,"REVERSE")==0)
		{
			int x,y;
			IO::read(x),IO::read(y);
			y=x+y,x--;
			x=kth(x),y=kth(y);
			splay(x,0),splay(y,x);
			Turn(sum[y].son[0]);
		}
		if(strcmp(op,"GET-SUM")==0)
		{
			int x,y;
			IO::read(x),IO::read(y);
			y=x+y,x--;
			x=kth(x),y=kth(y);
			splay(x,0),splay(y,x);
			IO::print(sum[sum[y].son[0]].sm,'\n');
		}
		if(strcmp(op,"MAX-SUM")==0)
		{
			int x=kth(0),y=kth(sum[Rt].sz-1);
			splay(x,0),splay(y,x);
			IO::print(sum[sum[y].son[0]].mx,'\n');
		}
	}
	return 0;
}

提交记录