/**************************************************************    Problem: 1500    User: 452181625    Language: C++    Result: Accepted    Time:7376 ms    Memory:25708 kb****************************************************************///参考网址：http://blog.163.com/chensmiles/blog/static/1214639912010111151243144 #include<iostream>#include<cstring>#include<cstdio>using namespace std;#define N 500010 int n,m,num[N];struct SplayTree{    int sz[N],ch[N][2],pre[N],que[N],sta[N];    int top1,top2,root;     int sum[N],maxm[N],maxl[N],maxr[N],val[N];    bool ro[N],same[N];     inline void SameNode(int x,int c)  //将以x为根的子树全部修改为c    {        if(x==0) return;        val[x]=c;        sum[x]=sz[x]*val[x];        maxm[x]=maxl[x]=maxr[x]=max(sum[x],val[x]);        same[x]=1; //延迟标记    }     inline void ReverseNode(int x) //将以x为根节点的子树翻转    {        if(x==0) return;        ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1];        maxl[x]^=maxr[x]^=maxl[x]^= maxr[x];        ro[x]^=1; //延迟标记    }     inline void PushDown(int x)    {        if(x==0) return;        if(ro[x])        {            ReverseNode(ch[x][0]);            ReverseNode(ch[x][1]);            ro[x]^=1;        }        if(same[x])        {            SameNode(ch[x][0],val[x]);            SameNode(ch[x][1],val[x]);            same[x]=0;        }    }     inline void PushUp(int x)    {        if(x==0) return;        sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];        sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]];        maxl[x]=max(maxl[ch[x][0]],sum[ch[x][0]]+val[x]+max(0,maxl[ch[x][1]]));        maxr[x]=max(maxr[ch[x][1]],sum[ch[x][1]]+val[x]+max(0,maxr[ch[x][0]]));        maxm[x]=max(max(maxl[ch[x][1]],0)+val[x]+max(maxr[ch[x][0]],0),max(maxm[ch[x][0]],maxm[ch[x][1]]));    }     inline void Rotate(int x,int c)     {        int y=pre[x];        PushDown(y);        PushDown(x);        ch[y][!c]=ch[x][c];        if(ch[x][c]) pre[ch[x][c]]=y;        pre[x]=pre[y];        if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;        ch[x][c]=y;        pre[y]=x;        PushUp(y);        if(y==root) root=x;    }     inline void Splay(int x,int f) //把x节点转到f节点的下面    {         PushDown(x);        while(pre[x]!=f)         {            PushDown(pre[pre[x]]);             PushDown(pre[x]);            PushDown(x);            if(pre[pre[x]]==f) Rotate(x,ch[pre[x]][0]==x); //单旋转            else            {                int y=pre[x],z=pre[y];                int c=(ch[z][0]==y);                if(ch[y][c]==x) Rotate(x,!c),Rotate(x,c); //之字型旋转                else Rotate(y,c),Rotate(x,c); //一字型旋转            }        }        PushUp(x);        if(f==0) root=x;    }     inline void SplayKth(int k,int f) //将第k个元素转到f节点的下面    {         int x=root;        k+=1;        while(1)        {            PushDown(x);            if(k==sz[ch[x][0]]+1) break;            else if(k<=sz[ch[x][0]]) x=ch[x][0];            else k-=sz[ch[x][0]]+1,x=ch[x][1];        }        Splay(x,f);    }     inline void Erase(int x) //删除以x节点为祖先的子树，回收内存    {         int head=1,rear=1;        que[head]=x;        while(head<=rear)        {            sta[++top2]=que[head];            if(ch[que[head]][0]) que[++rear]=ch[que[head]][0];            if(ch[que[head]][1]) que[++rear]=ch[que[head]][1];            head++;        }    }     void debug()    {        cout<<"root = "<<root<<endl;        traval(root);    }     void traval(int x)     {        if (x)        {            traval(ch[x][0]);            cout <<x<<" size: "<<sz[x]<<" left: "<<ch[x][0]<<" right: "<<ch[x][1]<<" pre: "<<pre[x]<<" val: "<<val[x]<<" sum: "<<sum[x]<<endl;            traval(ch[x][1]);        }    }     inline void NewNode(int &x,int c)    {        if(top2) x=sta[top2--];        else x=++top1;        ch[x][0]=ch[x][1]=pre[x]=0;        sz[x]=1;        ro[x]=same[x]=0;        val[x]=sum[x]=maxm[x]=maxl[x]=maxr[x]=c;    }     inline void Build(int &x,int l,int r,int f)     {        if(l>r) return;        int m=(l+r)>>1;        NewNode(x,num[m]);        Build(ch[x][0],l,m-1,x);        Build(ch[x][1],m+1,r,x);        pre[x]=f;        PushUp(x);    }     inline void Init(int n)     {        ch[0][0]=ch[0][1]=pre[0]=sz[0]=0;        ro[0]=same[0]=0;        maxr[0]=maxl[0]=maxm[0]=-1001;        sum[0]=0;        root=top1=top2=0;        for(int i=1;i<=n;i++) scanf("%d",&num[i]);        Build(root,0,n+1,0);    }     void GetSum()    {        int a,b;        scanf("%d%d",&a,&b);        SplayKth(a-1,0);        SplayKth(a+b,root);        printf("%d\n", sum[ch[ch[root][1]][0]]);    }     void MaxSum()    {        SplayKth(0, 0);        SplayKth(sz[root]-1,root);        printf("%d\n",maxm[ch[ch[root][1]][0]]);    }     void Insert() //插入区间、原理：将树旋转、第pos个数旋转到根、第pos+1个数到根的右孩子、然后再根的右孩子的左孩子处建树、因此结果是插入的数在第pos到pos+1之间、达到要求    {        int pos,tot;        scanf("%d%d",&pos,&tot);        for(int i=1;i<=tot;i++) scanf("%d", &num[i]);        SplayKth(pos,0);        SplayKth(pos+1,root);        Build(ch[ch[root][1]][0],1,tot,ch[root][1]);        PushUp(ch[root][1]);        PushUp(root);    }     void Delete() //删除区间、原理：将树旋转、第pos-1个数旋转到根、第pos+tot个数到根的右孩子、然后删除根的右孩子的左孩子即可    {        int pos,tot;        scanf("%d%d",&pos,&tot);        SplayKth(pos-1,0);        SplayKth(pos+tot,root);        Erase(ch[ch[root][1]][0]);        ch[ch[root][1]][0]=0;        PushUp(ch[root][1]);        PushUp(root);    }     void MakeSame()  //统一修改、原理：第pos-1个数旋转到根、第pos+tot个数到根的右孩子、然后将根的右孩子的左子树全部修改为c即可    {        int pos,tot,c;        scanf("%d%d%d",&pos,&tot,&c);        SplayKth(pos-1,0);        SplayKth(pos+tot,root);        SameNode(ch[ch[root][1]][0],c);    }     void Reverse()  //区间翻转、原理：第pos-1个数旋转到根、第pos+tot个数到根的右孩子、然后将根的右孩子的左子树翻转即可    {        int pos,tot;        scanf("%d%d",&pos,&tot);        SplayKth(pos-1,0);        SplayKth(pos+tot,root);        ReverseNode(ch[ch[root][1]][0]);    }}t; int main(){    char op[20];    scanf("%d%d",&n,&m);    t.Init(n);    while(m--)    {        scanf("%s",&op);        if(op[0]==‘G‘) t.GetSum();        else if(op[0]==‘M‘ && op[2]==‘X‘) t.MaxSum();        else if(op[0]==‘I‘) t.Insert();        else if(op[0]==‘D‘) t.Delete();        else if(op[0]==‘M‘ && op[2]==‘K‘) t.MakeSame();        else if(op[0]==‘R‘) t.Reverse();    }    return 0;}