debug到死2333.
虽然说是splay维护序列模板，作为蒟蒻的我还是GG
%%%考场A的dalao Orz Orz.
其实不开long long也行，inf开成0x3f3f3f3f也可（flag,欢迎推翻）
就当存个板子吧.
#include<bits/stdc++.h> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<deque> #include<list> #include<set> #include<vector> #include<iostream> #define ll long long #define re register #define inf 0x7f7f7f7f #define inl inline #define sqr(x) (x*x) #define max(a,b) (a>b?a:b) //#define eps 1e-8 #define debug puts("**************************"); //#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize (2) //#pragma G++ optimize (2) using namespace std; //const ll mod; const ll MAXN=1e6+10; inl ll read() { re ll x = 0; re int f = 1; char ch = getchar(); while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); } while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x * f; } inl char readc() { char ch=getchar(); while(('z'<ch||ch<'a')&&('Z'<ch||ch<'A')) ch=getchar(); return ch; } inl void write(re ll x){ if(x>=10)write(x/10); putchar(x%10+'0'); } inl void writeln(re ll x){ if(x<0) {x=-x;putchar('-');} write(x); puts(""); } inl ll gcd(re ll x,re ll y){while(y^=x^=y^=x%=y);return x;} inl ll Lcm(re ll a,re ll b) {return a/gcd(a,b)*b;} inl void FR() { freopen(".in","r",stdin); freopen(".out","w",stdout); } inl void FC() { fclose(stdin); fclose(stdout); } ll root,id[MAXN],cnt; struct Node { ll fa,son[2],sumx,val,siz,maxx,lx,rx; bool rev,flag; void clear() { fa=son[0]=son[1]=sumx=val=siz=maxx=lx=rx=rev=flag=0; } }Tree[MAXN]; ll dir(ll x) {return Tree[Tree[x].fa].son[1]==x;} inl void pushup(ll x) { re ll l=Tree[x].son[0],r=Tree[x].son[1]; Tree[x].siz=Tree[l].siz+Tree[r].siz+1; Tree[x].sumx=Tree[l].sumx+Tree[r].sumx+Tree[x].val; Tree[x].maxx=max(Tree[r].maxx,Tree[l].maxx); Tree[x].maxx=max(Tree[x].maxx,Tree[l].rx+Tree[r].lx+Tree[x].val); Tree[x].lx=max(Tree[l].lx,Tree[l].sumx+Tree[x].val+Tree[r].lx); Tree[x].rx=max(Tree[r].rx,Tree[r].sumx+Tree[x].val+Tree[l].rx); } inl void pushdown(ll x) { re ll l=Tree[x].son[0],r=Tree[x].son[1]; if(Tree[x].flag) { Tree[x].flag=Tree[x].rev=0; if(l) Tree[l].val=Tree[x].val,Tree[l].sumx=Tree[l].val*Tree[l].siz,Tree[l].flag=1; if(r) Tree[r].val=Tree[x].val,Tree[r].sumx=Tree[r].val*Tree[r].siz,Tree[r].flag=1; if(Tree[x].val>=0) { if(l) Tree[l].lx=Tree[l].rx=Tree[l].maxx=Tree[l].sumx; if(r) Tree[r].lx=Tree[r].rx=Tree[r].maxx=Tree[r].sumx; } else { if(l) Tree[l].lx=Tree[l].rx=0,Tree[l].maxx=Tree[l].val; if(r) Tree[r].lx=Tree[r].rx=0,Tree[r].maxx=Tree[r].val; } } if(Tree[x].rev) { Tree[x].rev=0;Tree[l].rev^=1;Tree[r].rev^=1; swap(Tree[l].lx,Tree[l].rx);swap(Tree[r].lx,Tree[r].rx); swap(Tree[l].son[0],Tree[l].son[1]); swap(Tree[r].son[0],Tree[r].son[1]); } } inl void rotate(ll x) { re ll y=Tree[x].fa,z=Tree[y].fa,o=dir(x); re ll so=dir(y); Tree[y].son[o]=Tree[x].son[o^1]; Tree[Tree[y].son[o]].fa=y; Tree[x].son[o^1]=y; Tree[y].fa=x; Tree[z].son[so]=x; Tree[x].fa=z; pushup(y);pushup(x); } inl void splay(ll x,ll goal) { for(re ll y;(y=Tree[x].fa)!=goal;rotate(x)) { if(Tree[y].fa!=goal) rotate(dir(y)==dir(x)?y:x); } if(!goal) root=x; } inl ll find(ll x,ll rk) { pushdown(x); re ll l=Tree[x].son[0],r=Tree[x].son[1]; if(Tree[l].siz+1==rk) return x; else if(Tree[l].siz>=rk) return find(l,rk); else return find(r,rk-Tree[l].siz-1); } ll s[MAXN]; inl ll build(ll l,ll r,ll fro) { re ll mid=(l+r)>>1,t=id[mid]; Tree[t].clear(); Tree[t].val=s[mid]; Tree[t].fa=fro; if(l==r) { Tree[t].lx=Tree[t].rx=max(0,Tree[t].val); Tree[t].maxx=Tree[t].sumx=Tree[t].val; Tree[t].son[0]=Tree[t].son[1]=0; Tree[t].siz=1; return t; } if(l<mid) Tree[t].son[0]=build(l,mid-1,t); else Tree[t].son[0]=0; if(mid<r) Tree[t].son[1]=build(mid+1,r,t); else Tree[t].son[1]=0; pushup(t); return t; } char ss[20]; queue<ll>Q; inl void insert(ll pos,ll tot) { for(re ll i=1;i<=tot;i++) s[i]=read(); for(re ll i=1;i<=tot;i++) { if(!Q.empty()) id[i]=Q.front(),Q.pop(); else id[i]=++cnt; } re ll l=find(root,pos+1),r=find(root,pos+2); splay(l,0);splay(r,l); Tree[r].son[0]=build(1,tot,r); pushup(r);pushup(l); } inl void recycle(ll x) { re ll &l=Tree[x].son[0],&r=Tree[x].son[1]; if(l) recycle(l); if(r) recycle(r); Q.push(x); Tree[x].clear();l=r=0; } inl ll split(ll pos,ll tot) { re ll x=find(root,pos),y=find(root,pos+tot+1); splay(x,0);splay(y,x); return Tree[y].son[0]; } inl void del(ll pos,ll tot) { re ll x=split(pos,tot),y=Tree[x].fa; recycle(x);Tree[y].son[0]=0; pushup(y);pushup(Tree[y].fa); } inl void modify(ll pos,ll tot,ll val) { re ll x=split(pos,tot),y=Tree[x].fa; Tree[x].flag=1; Tree[x].val=val,Tree[x].sumx=Tree[x].siz*Tree[x].val; if(Tree[x].val>=0) Tree[x].lx=Tree[x].rx=Tree[x].maxx=Tree[x].sumx; else Tree[x].lx=Tree[x].rx=0,Tree[x].maxx=Tree[x].val; pushup(y);pushup(Tree[y].fa); } inl void rever(ll pos,ll tot) { re ll x=split(pos,tot),y=Tree[x].fa; if(!Tree[x].flag) { Tree[x].rev^=1; swap(Tree[x].lx,Tree[x].rx); swap(Tree[x].son[0],Tree[x].son[1]); pushup(y);pushup(Tree[y].fa); } } inl ll query(ll pos,ll tot) { re ll x=split(pos,tot); return Tree[x].sumx; } int main() { // FR(); re ll n=read(),m=read(); for(re ll i=1;i<=n;i++) {s[i+1]=read();} Tree[0].maxx=s[1]=s[n+2]=-inf;cnt=n+2; for(re ll i=1;i<=n+2;i++) id[i]=i; root=build(1,n+2,0); for(re ll i=1;i<=m;i++) { scanf("%s",ss); if(ss[0]=='I') { re ll pos=read(),tot=read(); insert(pos,tot); } else if(ss[0]=='D') { re ll pos=read(),tot=read(); del(pos,tot); } else if(ss[0]=='M') { if(ss[2]=='X') writeln(Tree[root].maxx); else { re ll pos=read(),tot=read(),val=read(); modify(pos,tot,val); } } else if(ss[0]=='R') { re ll pos=read(),tot=read(); rever(pos,tot); } else if(ss[0]=='G') { re ll pos=read(),tot=read(); writeln(query(pos,tot)); } } // FC(); return 0; }