[NOI2005] 维护数列

题目描述

请写一个程序,要求维护一个数列,支持以下 $6$ 种操作: | 编号 | 名称 | 格式 | 说明 | | :-----------: | :-----------: | :-----------: | :----------- | | 1 | 插入 | $\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}$ | 在当前数列的第 $posi$ 个数字后插入 $tot$ 个数字:$c_1, c_2 \cdots c_{tot}$;若在数列首插入,则 $posi$ 为 $0$ | | 2 | 删除 | $\operatorname{DELETE} \ posi \ tot$ | 从当前数列的第 $posi$ 个数字开始连续删除 $tot$ 个数字 | | 3 | 修改 | $\operatorname{MAKE-SAME} \ posi \ tot \ c$ | 从当前数列的第 $posi$ 个数字开始的连续 $tot$ 个数字统一修改为 $c$ | | 4 | 翻转 | $\operatorname{REVERSE} \ posi \ tot$ | 取出从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字,翻转后放入原来的位置 | | 5 | 求和 | $\operatorname{GET-SUM} \ posi \ tot$ | 计算从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字的和并输出 | | 6 | 求最大子列和 | $\operatorname{MAX-SUM}$ | 求出当前数列中和最大的一段子列,并输出最大和 |

输入输出格式

输入格式


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

输出格式


对于输入数据中的 $\operatorname{GET-SUM}$ 和 $\operatorname{MAX-SUM}$ 操作,向输出文件依次打印结果,每个答案(数字)占一行。

输入输出样例

输入样例 #1

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

-1
10
1
10

说明

#### 数据规模与约定 - 你可以认为在任何时刻,数列中至少有 $1$ 个数。 - 输入数据一定是正确的,即指定位置的数在数列中一定存在。 - 对于 $50\%$ 的数据,任何时刻数列中最多含有 $3 \times 10^4$ 个数。 - 对于 $100\%$ 的数据,任何时刻数列中最多含有 $5 \times 10^5$ 个数,任何时刻数列中任何一个数字均在 $[-10^3, 10^3]$ 内,$1 \le M \le 2 \times 10^4$,插入的数字总数不超过 $4 \times 10^6$。 题面由 @syksykCCC 提供。