#146. 「NOI2005」维护数列

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

请写一个程序,要求维护一个数列,支持以下 6 种操作。

操作 输入格式 说明
插入 INSERT pos cnt a[1] a[2] ...... a[cnt] 在当前数列的第 \text{pos} 个数字后插入 \text{cnt} 个数字: a_1, a_2 \ldots, a_{\text{cnt}} ,如果 \text{pos} = 0 ,则在首部插入
删除 DELETE pos cnt 从当前数列的第 \text{pos} 个数字开始,删除连续的 \text{cnt} 个数字
修改 MAKE-SAME pos cnt x 将当前数列的第 \text{pos} 个数字开始的连续 \text{cnt} 个数字统一修改为 x
翻转 REVERSE pos cnt 取出当前数列的第 \text{pos} 个数字开始的连续 \text{cnt} 个数字,翻转后放入原来的位置
求和 GET-SUM pos cnt x 计算从当前数列的第 \text{pos} 个数字开始的连续 \text{cnt} 个数字的和并输出
最大子段和 MAX-SUM 求出当前数列中和最大的一段子序列,并输出其和

输入格式

输入的第一行包含两个数 N M N 表示初始时数列中数的个数, M 表示要进行的操作数目。
第二行包含 N 个数字,描述初始时的数列。
以下 M 行,每行一条命令,格式参见问题描述中的表格。

输出格式

对于输入数据中的 GET-SUMMAX-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

数据范围与提示

1 \leq N \leq 500000, 1 \leq M \leq 20000
任何时刻数列中最多含有 500000 个数,数列中任何一个数字均在 [-1000, 1000] 内;
插入的数字总数不超过 4 \times 10 ^ 6 个,输入文件大小不超过 20 \ \text{MBytes}