splay乱搞。
调了两个多小时。。。这辈子再也不想写splay了。。。
维护左边最大连续和右边最大连续，维护两个标记，无脑push_down、push_up就行了。
注意最大连续和至少要包含一个数。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500010
#define M 5000005
#define inf 0x3f3f3f3f
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
using namespace std;
int n,m;
int cnt;
int a[N],root,ch[N][],tmproot;
int sum[N],ls[N],rs[N],mx[N],ji[N];
int lazy[N],size[N],zhi[N],fa[N];
int s[M],tot2;
inline int mxx(int x,int y)
{
if(x>y)return x;return y;
}
// ls 左边最大 rs 右边最大
void push_up(int x)
{
size[x]=size[lc(x)]+size[rc(x)]+;
sum[x]=sum[lc(x)]+sum[rc(x)]+zhi[x];
mx[x]=mxx(mx[lc(x)],mxx(mx[rc(x)],zhi[x]+rs[lc(x)]+ls[rc(x)]));
ls[x]=mxx(,mxx(ls[lc(x)],sum[lc(x)]+zhi[x]+ls[rc(x)]));
rs[x]=mxx(,mxx(rs[rc(x)],sum[rc(x)]+zhi[x]+rs[lc(x)]));
return ;
}
void push_down(int x)
{
int l=ch[x][];int r=ch[x][];
if(ji[x]!=-)
{
ji[l]=ji[r]=ji[x];
sum[l]=size[l]*ji[x];sum[r]=size[r]*ji[x];
zhi[l]=zhi[r]=ji[x];
if(ji[x]>)ls[l]=rs[l]=mx[l]=sum[l],ls[r]=rs[r]=mx[r]=sum[r];
else ls[l]=rs[l]=,ls[r]=rs[r]=,mx[l]=mx[r]=ji[x];
ji[x]=-;
}
if(lazy[x]==)
{
lazy[l]^=;lazy[r]^=;
swap(ch[l][],ch[l][]);
swap(ch[r][],ch[r][]);
swap(ls[l],rs[l]);swap(ls[r],rs[r]);
lazy[x]=;
}
sum[]=ls[]=rs[]=;mx[]=-inf;
return ;
}
void build(int x,int l,int r)
{
if(l==r)
{
size[x]=;
sum[x]=zhi[x]=mx[x]=a[l];
rs[x]=ls[x]=max(,a[l]);
return ;
}
int mid=(l+r)>>;
if(l!=mid)
{
if(tot2)ch[x][]=s[tot2--];
else ch[x][]=++cnt;
fa[ch[x][]]=x,build(ch[x][],l,mid-);
}
if(tot2)ch[x][]=s[tot2--];
else ch[x][]=++cnt;
fa[ch[x][]]=x,build(ch[x][],mid+,r);
zhi[x]=a[mid];
push_up(x);
}
void rotate(int p)
{
int q=fa[p],y=fa[q],x=(ch[q][]==p);
ch[q][x]=ch[p][x^];fa[ch[q][x]]=q;
ch[p][x^]=q;fa[q]=p;
fa[p]=y;
if(y)
{
if(ch[y][]==q)ch[y][]=p;
else ch[y][]=p;
}
push_up(q);
return ;
}
void splay(int x,int yy)
{
for(int y;y=fa[x];rotate(x))
{
if(y==yy)break;
if(fa[y]!=yy)
{
if((lc(fa[y])==y&&lc(y)==x)||(rc(fa[y])==y&&rc(y)==x))rotate(y);
else rotate(x);
}
}
push_up(x);
if(!yy)root=x;
}
int find(int k,int x)
{
push_down(k);
int l=lc(k),r=rc(k);
if(size[l]+==x)return k;
if(size[l]+>x)return find(l,x);
else return find(r,x-size[l]-);
}
char c[];
void dfs(int x)
{
if(!x)return ;
cout<<zhi[x]<<' '<<sum[x]<<' '<<size[x]<<endl;
dfs(ch[x][]);dfs(ch[x][]);
}
void del(int x)
{
if(!x)return ;
s[++tot2]=x;ji[x]=-;lazy[x]=;sum[x]=;
del(ch[x][]);del(ch[x][]);
ch[x][]=ch[x][]=;fa[x]=;size[x]=;
}
int main()
{
scanf("%d%d",&n,&m);
mx[]=-inf;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<N;i++)ji[i]=-;
root=++cnt;
a[]=a[n+]=;
build(cnt,,n+);
int t1,t2,t3,t4,t5,t6;
for(int i=;i<=m;i++)
{
scanf("%s",c);
if(c[]=='I')
{
scanf("%d%d",&t1,&t2);
for(int j=;j<=t2;j++)scanf("%d",&a[j]);
if(tot2)tmproot=s[tot2--];
else tmproot=++cnt;
build(tmproot,,t2);
t1++;t3=find(root,t1);
splay(t3,);
t4=ch[t3][];push_down(t4);
while(ch[t4][])t4=ch[t4][],push_down(t4);
splay(t4,t3);ch[t4][]=tmproot;fa[tmproot]=t4;push_up(t4);push_up(t3);
}
else if(c[]=='D')
{
scanf("%d%d",&t1,&t2);
t3=find(root,t1);
splay(t3,);
t2=t2+t1+;
t4=find(root,t2);
splay(t4,t3);
del(ch[t4][]);
ch[t4][]=;
push_up(t4);push_up(t3);
}
else if(c[]=='R')
{
scanf("%d%d",&t1,&t2);
t3=find(root,t1);splay(t3,);t2=t2+t1+;t4=find(root,t2);
splay(t4,t3);
t5=ch[t4][];
lazy[t5]^=;swap(ch[t5][],ch[t5][]);swap(ls[t5],rs[t5]);
push_up(t4);push_up(t3);
}
else if(c[]=='G')
{
scanf("%d%d",&t1,&t2);
t3=find(root,t1);
splay(t3,);t2=t2+t1+;
t4=find(root,t2);
splay(t4,t3);
printf("%d\n",sum[ch[t4][]]);
}
else if(c[]=='M'&&c[]=='S')
{
t1=find(root,);
splay(t1,);
t2=find(root,size[root]);
splay(t2,t1);
printf("%d\n",mx[ch[t2][]]);
}
else
{
scanf("%d%d%d",&t1,&t2,&t6);
t3=find(root,t1);splay(t3,);t2=t2+t1+;
t4=find(root,t2);
splay(t4,t3);
t5=ch[t4][];
ji[t5]=t6;zhi[t5]=t6;sum[t5]=size[t5]*t6;
if(t6>)ls[t5]=rs[t5]=mx[t5]=sum[t5];
else ls[t5]=rs[t5]=,mx[t5]=t6;
push_up(t4);push_up(t3);
}
}
return ;
}