1 #include<bits/stdc++.h>
  2 #define dbg(x) cerr << #x << " = " << x <<endl
  3 using namespace std;
  4 typedef long long ll;
  5 template<typename T>inline T _min(T A,T B){return A>B?B:A;}
  6 template<typename T>inline T _max(T A,T B){return A<B?B:A;}
  7 template<typename T>inline T _max(T A,T B,T C){return _max(_max(A,B),C);}
  8 template<typename T>inline void _swap(T&a,T&b){a^=b^=a^=b;}
  9 template<typename T>inline int read(T&x){
 10     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c==‘-‘)f=1;
 11     while(isdigit(c))x=x*10+c-‘0‘,c=getchar();return f?x=-x:x;
 12 }
 13 const int N=550000+7,INF=5e8;
 14 struct tree{
 15     int ch[2],f,siz,val,sam,rev,sum,ls,rs,ms;
 16 }T[N];
 17 queue<int> q;
 18 int id[N],A[N];
 19 int n,m,tot,rt,len;
 20 
 21 inline int dir(int x){return T[T[x].f].ch[1]==x;}
 22 inline void pushup(int x){//MISTAKE:the max sum can‘t be empty.
 23     int l=T[x].ch[0],r=T[x].ch[1];
 24     T[x].siz=T[l].siz+T[r].siz+1;
 25     T[x].sum=T[l].sum+T[r].sum+T[x].val;
 26     T[x].ls=_max(T[l].ls,T[l].sum+T[x].val+T[r].ls);
 27     T[x].rs=_max(T[r].rs,T[r].sum+T[x].val+T[l].rs);//MISTAKE occured when copying.
 28     T[x].ms=_max(T[l].ms,T[r].ms,T[l].rs+T[x].val+T[r].ls); 
 29 //    dbg(x),dbg(l),dbg(r),dbg(T[x].sum),dbg(T[x].siz);
 30 }
 31 inline void pushdown(int x){
 32     int l=T[x].ch[0],r=T[x].ch[1];
 33     if(T[x].sam^(-INF)){
 34         T[l].val=T[r].val=T[l].sam=T[r].sam=T[x].sam;
 35         T[l].sum=T[l].siz*T[l].sam,T[r].sum=T[r].siz*T[r].sam;
 36         if(T[x].sam>0)T[l].ls=T[l].rs=T[l].ms=T[l].sum,T[r].ls=T[r].rs=T[r].ms=T[r].sum;
 37         else T[l].ls=T[l].rs=T[r].ls=T[r].rs=0,T[l].ms=T[r].ms=T[x].sam;
 38         T[x].sam=-INF,T[x].rev=0;
 39     }
 40     if(T[x].rev){
 41         T[x].rev=0,T[l].rev^=1,T[r].rev^=1;
 42         _swap(T[l].ch[0],T[l].ch[1]),_swap(T[r].ch[0],T[r].ch[1]);//MISTAKE:again:typo.
 43         _swap(T[l].ls,T[l].rs),_swap(T[r].ls,T[r].rs);//!MISTAKE:when giving down‘rev‘tag,update children at once!
 44     }
 45 }
 46 inline void Rotate(int x){
 47     int y=T[x].f,z=T[y].f,d=dir(x);
 48     T[y].ch[d]=T[x].ch[d^1],T[T[x].ch[d^1]].f=y;
 49     T[z].ch[dir(y)]=x,T[x].f=z;
 50     T[x].ch[d^1]=y,T[y].f=x;pushup(y),pushup(x);
 51 }
 52 inline void Splay(int x,int to){
 53     while(T[x].f^to){if(T[T[x].f].f^to) dir(T[x].f)^dir(x)?Rotate(x):Rotate(T[x].f);Rotate(x);}
 54     if(!to)rt=x;
 55 }
 56 int Query_kth(int x,int k){
 57     pushdown(x);
 58     if(k<=T[T[x].ch[0]].siz)return Query_kth(T[x].ch[0],k);
 59     else if(k==T[T[x].ch[0]].siz+1)return x;
 60     return Query_kth(T[x].ch[1],k-T[T[x].ch[0]].siz-1);
 61 }
 62 inline void Spilt(int l,int r){
 63     l=Query_kth(rt,l),r=Query_kth(rt,r);
 64     Splay(l,0),Splay(r,l);//cerr<<"spilt:"<<endl;dbg(l),dbg(r);
 65 }
 66 void Build(int L,int R,int&x,int fa){
 67     int mid=L+R>>1;
 68     x=id[mid],T[x].siz=1,T[x].val=A[mid],T[x].f=fa;
 69     T[x].sam=-INF,T[x].rev=0;//MISTAKE:the lazy-tag which represents‘MAKE_SAME‘ can‘t be zero at first.
 70     if(L==R){
 71         T[x].sum=T[x].val;T[x].ms=T[x].val;
 72         T[x].val>0?(T[x].ls=T[x].rs=T[x].val):(T[x].ls=T[x].rs=0);
 73     //    dbg(x),dbg(T[x].sum),dbg(T[x].ls),dbg(T[x].rs),dbg(T[x].ms);
 74         return;
 75     }
 76     if(L<mid)Build(L,mid-1,T[x].ch[0],x);if(mid<R)Build(mid+1,R,T[x].ch[1],x);pushup(x);
 77 }
 78 void prebuild(int L,int R,int&x,int fa){
 79     int mid=L+R>>1;x=id[mid],T[x].siz=1,T[x].val=A[mid],T[x].f=fa,T[x].sam=-INF;
 80     if(L==R){
 81         T[x].sum=T[x].val;T[x].ms=T[x].val;if(x==1||x==n+2)T[x].ms=-INF;
 82         T[x].val>0?(T[x].ls=T[x].rs=T[x].val):(T[x].ls=T[x].rs=0);
 83         return;
 84     }
 85     if(L<mid)prebuild(L,mid-1,T[x].ch[0],x);if(mid<R)prebuild(mid+1,R,T[x].ch[1],x);pushup(x);
 86 }
 87 inline void Insert(int x,int cnt){
 88     for(register int i=1;i<=cnt;++i){
 89         read(A[i]);
 90         if(q.empty())id[i]=++tot;
 91         else id[i]=q.front(),q.pop();
 92     }
 93     Spilt(x+1,x+2);Build(1,cnt,T[T[rt].ch[1]].ch[0],T[rt].ch[1]);
 94     pushup(T[rt].ch[1]),pushup(rt);//MISTAKE:DON‘T  FORGET  PUSHUP!
 95 }
 96 inline void Erase(int&x){
 97     if(!x)return;
 98     Erase(T[x].ch[0]),Erase(T[x].ch[1]);
 99     q.push(x);x=0;
100 }
101 inline void Delete(int x,int cnt){
102     Spilt(x,x+cnt+1);Erase(T[T[rt].ch[1]].ch[0]);
103     pushup(T[rt].ch[1]),pushup(rt);
104 }
105 inline void make_same(int x,int cnt){
106     Spilt(x,x+cnt+1);int y=T[T[rt].ch[1]].ch[0],c;read(c);
107     T[y].val=c,T[y].sam=c,T[y].sum=T[y].siz*c;
108     c>0?(T[y].ls=T[y].rs=T[y].ms=T[y].sum):(T[y].ls=T[y].rs=0,T[y].ms=c);//MISTAKE:‘y‘,not ‘x‘! 
109     pushup(T[rt].ch[1]);pushup(rt);
110 }
111 inline void Reverse(int x,int cnt){
112     Spilt(x,x+cnt+1);int y=T[T[rt].ch[1]].ch[0];
113     T[y].rev^=1;_swap(T[y].ch[0],T[y].ch[1]),_swap(T[y].ls,T[y].rs);
114 }
115 inline void Query_sum(int x,int cnt){Spilt(x,x+cnt+1);printf("%d\n",T[T[T[rt].ch[1]].ch[0]].sum);}
116 inline void Query_max_sum(){Spilt(1,len+2);printf("%d\n",T[T[T[rt].ch[1]].ch[0]].ms);}
117 char s[15];int pos,cnt;
118 
119 int main(){//freopen("ttt.in","r",stdin);//freopen(".out","w",stdout);
120     len=read(n),read(m);
121     for(register int i=1;i<=n;++i)read(A[i+1]),id[i+1]=i+1;
122     id[1]=1,id[n+2]=n+2;tot=n+2;T[0].ms=-INF;//T[0].ms must be set zero!Think about the situation that a point has only one child when pushuping. 
123     prebuild(1,n+2,rt,0);
124     while(m--){
125         scanf("%s",s);
126         if(s[0]==‘I‘)read(pos),read(cnt),Insert(pos,cnt),len+=cnt;
127         else if(s[0]==‘D‘)read(pos),read(cnt),Delete(pos,cnt),len-=cnt;
128         else if(s[2]==‘K‘)read(pos),read(cnt),make_same(pos,cnt);
129         else if(s[0]==‘R‘)read(pos),read(cnt),Reverse(pos,cnt);
130         else if(s[0]==‘G‘)read(pos),read(cnt),Query_sum(pos,cnt);
131         else Query_max_sum();
132     }
133     return 0;
134 }