输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

#include<cstdio>#include<queue>using namespace std;int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}const int N=1e6+5;const int inf=0x3f3f3f3f;//1Wint n,m,rt,cnt,a[N],id[N],fa[N],c[N][2];int sum[N],siz[N],v[N],mx[N],lx[N],rx[N];bool tag[N],rev[N];queue<int>q;void updata(int x){    int l=c[x][0],r=c[x][1];    sum[x]=sum[l]+sum[r]+v[x];    siz[x]=siz[l]+siz[r]+1;    mx[x]=max(mx[l],mx[r]);    mx[x]=max(mx[x],lx[r]+rx[l]+v[x]);    lx[x]=max(lx[l],sum[l]+lx[r]+v[x]);    rx[x]=max(rx[r],sum[r]+rx[l]+v[x]);}void pushdown(int x){    int l=c[x][0],r=c[x][1];    if(tag[x]){        tag[x]=rev[x]=0;        if(l) tag[l]=1,v[l]=v[x],sum[l]=v[x]*siz[l];        if(r) tag[r]=1,v[r]=v[x],sum[r]=v[x]*siz[r];        if(v[x]>=0){            if(l) lx[l]=rx[l]=mx[l]=sum[l];            if(r) lx[r]=rx[r]=mx[r]=sum[r];        }        else{            if(l) lx[l]=rx[l]=0,mx[l]=sum[l];            if(r) lx[r]=rx[r]=0,mx[r]=sum[r];        }    }    if(rev[x]){        rev[x]^=1;rev[l]^=1;rev[r]^=1;        swap(lx[l],rx[l]);swap(lx[r],rx[r]);        swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);    }}void rotate(int x,int &k){    int y=fa[x],z=fa[y],l,r;    l=(c[y][1]==x);r=l^1;    if(y==k) k=x;    else c[z][c[z][1]==y]=x;    fa[x]=z;fa[y]=x;fa[c[x][r]]=y;    c[y][l]=c[x][r];c[x][r]=y;    updata(y);updata(x);}void splay(int x,int &k){    while(x!=k){        int y=fa[x],z=fa[y];        if(y!=k){            if((c[y][0]==x)^(c[z][0]==y)) rotate(x,k);            else rotate(y,k);        }        rotate(x,k);    }}void rec(int x){    if(!x) return ;    int l=c[x][0],r=c[x][1];    rec(l);rec(r);    q.push(x);    fa[x]=c[x][0]=c[x][1]=0;    tag[x]=rev[x]=0;}int find(int x,int rk){    pushdown(x);    int l=c[x][0],r=c[x][1];    if(siz[l]+1==rk) return x;    if(siz[l]>=rk) return find(l,rk);    else return find(r,rk-siz[l]-1);}int split(int k,int tot){    int x=find(rt,k),y=find(rt,k+tot+1);    splay(x,rt);splay(y,c[x][1]);    return c[y][0];}void modify(int k,int tot,int val){    int x=split(k,tot),y=fa[x];    v[x]=val;tag[x]=1;sum[x]=siz[x]*val;    if(val>=0) lx[x]=rx[x]=mx[x]=sum[x];    else lx[x]=rx[x]=0,mx[x]=val;    updata(y),updata(fa[y]);}void rever(int k,int tot){    int x=split(k,tot),y=fa[x];    if(!tag[x]){        rev[x]^=1;        swap(lx[x],rx[x]);        swap(c[x][0],c[x][1]);        updata(y);updata(fa[y]);    }}void erase(int k,int tot){    int x=split(k,tot),y=fa[x];    rec(x);    c[y][0]=0;    updata(y);updata(fa[y]);}void query(int k,int tot){    int x=split(k,tot);    printf("%d\n",sum[x]);}void build(int l,int r,int f){    if(l>r) return ;    int mid=l+r>>1,now=id[mid],last=id[f];    if(l==r){        sum[now]=a[l];siz[now]=1;        tag[now]=rev[now]=0;        if(a[l]>=0) lx[now]=rx[now]=mx[now]=a[l];        else lx[now]=rx[now]=0,mx[now]=a[l];    }    else build(l,mid-1,mid),build(mid+1,r,mid);    v[now]=a[mid];fa[now]=last;c[last][mid>=f]=now;    updata(now);}void insert(int k,int tot){    for(int i=1;i<=tot;i++) a[i]=read();    for(int i=1;i<=tot;i++){        if(!q.empty()) id[i]=q.front(),q.pop();        else id[i]=++cnt;    }    build(1,tot,0);    int z=id[tot+1>>1];    int x=find(rt,k+1),y=find(rt,k+2);    splay(x,rt);splay(y,c[x][1]);    fa[z]=y;c[y][0]=z;    updata(y);updata(x);}int main(){    n=read();m=read();    mx[0]=a[1]=a[n+2]=-inf;    for(int i=2;i<=n+1;i++) a[i]=read();    for(int i=1;i<=n+2;i++) id[i]=i;    build(1,n+2,0);    rt=n+3>>1;cnt=n+2;    char s[10];    for(int i=1,k,tot,val;i<=m;i++){        scanf("%s",s);        if(s[0]!=‘M‘||s[2]!=‘X‘) k=read(),tot=read();        if(s[0]==‘I‘) insert(k,tot);        if(s[0]==‘D‘) erase(k,tot);        if(s[0]==‘R‘) rever(k,tot);        if(s[0]==‘G‘) query(k,tot);        if(s[0]==‘M‘){            if(s[2]==‘X‘) printf("%d\n",mx[rt]);            else val=read(),modify(k,tot,val);        }    }    return 0;}