内存限制：256 MB
【问题描述】
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
|
操作编号 |
输入文件中的格式 |
说明 |
|
1. 插入 |
INSERT_posi_tot_c1_c2_..._ctot |
在当前数列的第 posi 个数字后插入 tot 个数字：c1, c2, …, ctot；若在数列首插 入，则 posi 为 0 |
|
2. 删除 |
DELETE_posi_tot |
从当前数列的第 posi 个数字开始连续 删除 tot 个数字 |
|
3. 修改 |
MAKE-SAME_posi_tot_c |
将当前数列的第 posi 个数字开始的连 续 tot 个数字统一修改为 c |
|
4. 翻转 |
REVERSE_posi_tot |
取出从当前数列的第 posi 个数字开始 的 tot 个数字，翻转后放入原来的位置 |
|
5. 求和 |
GET-SUM_posi_tot |
计算从当前数列开始的第 posi 个数字 开始的 tot 个数字的和并输出 |
|
6. 求和最 大的子列 |
MAX-SUM |
求出当前数列中和最大的一段子列， 并输出最大和 |
【输入格式】
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第 2 行包含 N 个数字，描述初始时的数列。
以下 M 行，每行一条命令，格式参见问题描述中的表格。
【输出格式】
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。
【输入样例】
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
【输出样例】
-1
10
1
10
【样例说明】
初始时，我们拥有数列 2 -6 3 5 1 -5 -3 6 3
执行操作 GET-SUM 5 4，表示求出数列中从第 5 个数开始连续 4 个数字之和，1+(-5)+(-3)+6 = -1：
2 -6 3 5 1 -5 -3 6 3
执行操作 MAX-SUM，表示要求求出当前数列中最大的一段和，应为 3+5+1+(-5)+(-3)+6+3 = 10：
2 -6 3 5 1 -5 -3 6 3
执行操作 INSERT 8 3 -5 7 2，即在数列中第 8 个数字后插入-5 7 2，
2 -6 3 5 1 -5 -3 6 -5 7 2 3
执行操作 DELETE 12 1，表示删除第 12 个数字，即最后一个：
2 -6 3 5 1 -5 -3 6 -5 7 2
执行操作 MAKE-SAME 3 3 2，表示从第 3 个数开始的 3 个数字，统一修改为 2：
2 -6 3 5 1 -5 -3 6 -5 7 2
改为
2 -6 2 2 2 -5 -3 6 -5 7 2
执行操作 REVERSE 3 6，表示取出数列中从第 3 个数开始的连续 6 个数：
2 -6 2 2 2 -5 -3 6 -5 7 2
如上所示的灰色部分 2 2 2 -5 -3 6，翻转后得到 6 -3 -5 2 2 2，并放回原来位置：
2 -6 6 -3 -5 2 2 2 -5 7 2
最后执行 GET-SUM 5 4 和 MAX-SUM，不难得到答案 1 和 10。
2 -6 6 -3 -5 2 2 2 -5 7 2
【评分方法】
本题设有部分分，对于每一个测试点：
- 如果你的程序能在输出文件正确的位置上打印 GET-SUM 操作的答案，你可以得到该测试点 60%的分数；
- 如果你的程序能在输出文件正确的位置上打印 MAX-SUM 操作的答案，你可以得到该测试点 40%的分数；
- 以上两条的分数可以叠加，即如果你的程序正确输出所有 GET-SUM 和MAX-SUM 操作的答案，你可以得到该测试点 100%的分数。
请注意：如果你的程序只能正确处理某一种操作，请确定在输出文件正确的位置上打印结果，即必须为另一种操作留下对应的行，否则我们不保证可以正确评分。
【数据规模和约定】
- 你可以认为在任何时刻，数列中至少有 1 个数。
- 输入数据一定是正确的，即指定位置的数在数列中一定存在。
- 50%的数据中，任何时刻数列中最多含有 30 000 个数；
- 100%的数据中，任何时刻数列中最多含有 500 000 个数。
- 100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
- 100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 个，输入文件大小不超过 20MBytes。
这道题需要注意细节，写之前请理清思路！！！
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
const int INF=;
int fa[maxn],ch[maxn][],sz[maxn],key[maxn];
int mark[maxn],flip[maxn],sum[maxn],n,Q;
int lx[maxn],rx[maxn],mx[maxn],rt,cnt;
char s[];
void Push_up(int x){
sz[x]=sz[ch[x][]]+sz[ch[x][]]+;
sum[x]=sum[ch[x][]]+sum[ch[x][]]+key[x];
lx[x]=max(lx[ch[x][]],key[x]+sum[ch[x][]]+lx[ch[x][]]);
rx[x]=max(rx[ch[x][]],key[x]+sum[ch[x][]]+rx[ch[x][]]);
mx[x]=max(max(mx[ch[x][]],mx[ch[x][]]),key[x]+rx[ch[x][]]+lx[ch[x][]]);
} void Cover(int x,int d){
if(!x)return;
key[x]=d;mark[x]=;
sum[x]=sz[x]*d;
if(d>)lx[x]=rx[x]=mx[x]=sum[x];
else lx[x]=rx[x]=,mx[x]=d;
} void Flip(int x){
if(!x)return;
swap(ch[x][],ch[x][]);
swap(lx[x],rx[x]); //mod Kuang_bin
flip[x]^=;
} void Push_down(int x){
if(mark[x]){
Cover(ch[x][],key[x]);
Cover(ch[x][],key[x]);
mark[x]=;
}
if(flip[x]){
Flip(ch[x][]);
Flip(ch[x][]);
flip[x]=;
}
} void Rotate(int x){
int y=fa[x],g=fa[y],c=ch[y][]==x;
ch[y][c]=ch[x][c^];fa[ch[y][c]]=y;
ch[x][c^]=y;fa[y]=x;fa[x]=g;
if(g)ch[g][ch[g][]==y]=x;
Push_up(y);
} void Splay(int x,int g=){
for(int y;(y=fa[x])!=g;Rotate(x))
if(fa[y]!=g)
Rotate((ch[fa[y]][]==y)==(ch[y][]==x)?y:x);
if(!g)rt=x;
Push_up(x);
} void Rtr(int k,int g=){
int p=rt;
while(true){
Push_down(p);
if(sz[ch[p][]]+==k)break;
if(sz[ch[p][]]+<k){
k-=sz[ch[p][]]+;
p=ch[p][];
}
else
p=ch[p][];
}
Splay(p,g);
} int Insert(int x,int l,int r){
int mid=(l+r)>>,p=++cnt;
fa[p]=x;sz[p]=;
if(l<mid)ch[p][]=Insert(p,l,mid-);
scanf("%d",&key[p]);
if(r>mid)ch[p][]=Insert(p,mid+,r);
Push_up(p);
return p;
} void Init(){
cnt=;rt=;
mx[]=mx[]=-INF;
fa[]=;ch[][]=;
ch[ch[rt][]][]=Insert(ch[rt][],,n);
Push_up(ch[rt][]);
Push_up(rt);
} int main(){
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
scanf("%d%d",&n,&Q);
Init();mx[]=-INF;
int l,r,x,d,tot=n+;
while(Q--){
scanf("%s",s);
if(!strcmp(s,"MAX-SUM")){
Rtr();
Rtr(tot,rt);
Push_down(rt);
Push_down(ch[rt][]);
printf("%d\n",mx[ch[ch[rt][]][]]);
}
else if(!strcmp(s,"INSERT")){
scanf("%d%d",&l,&x);l+=;
Rtr(l);Rtr(l+,rt);
Push_down(rt);tot+=x;
Push_down(ch[rt][]);
ch[ch[rt][]][]=Insert(ch[rt][],,x);
Push_up(ch[rt][]);
Push_up(rt);
}
else if(!strcmp(s,"DELETE")){
scanf("%d%d",&l,&x);r=l+x+;
Rtr(l);Rtr(r,rt);tot-=x;
ch[ch[rt][]][]=;
Push_up(ch[rt][]);
Push_up(rt);
}
else if(!strcmp(s,"REVERSE")){
scanf("%d%d",&l,&x);r=l+x+;
Rtr(l);Rtr(r,rt);
Flip(ch[ch[rt][]][]);
Push_up(ch[rt][]);
Push_up(rt);
}
else if(!strcmp(s,"MAKE-SAME")){
scanf("%d%d%d",&l,&x,&d);r=l+x+;
Rtr(l);Rtr(r,rt);
Push_down(rt);
Push_down(ch[rt][]);
Cover(ch[ch[rt][]][],d);
Push_up(ch[rt][]);
Push_up(rt);
}
else if(!strcmp(s,"GET-SUM")){
scanf("%d%d",&l,&x);r=l+x+;
Rtr(l);Rtr(r,rt);
Push_down(rt);
Push_down(ch[rt][]);
printf("%d\n",sum[ch[ch[rt][]][]]);
}
}
return ;
}