Comet OJ

C0318 [NOI2005Day1-B]维护数列

内存限制：256 MB 时间限制：1000 ms

题目描述

请写一个程序，要求维护一个数列，支持以下6种操作：（请注意，格式栏中的下划线‘_’表示实际输入文件中的空格）

屏幕快照 2019-06-10 下午8.44.56.png

输入格式

第1行包含两个数$N$和$M$，$N$表示初始时数列中数的个数，$M$表示要进行的操作数目。

第2行包含$N$个数字，描述初始时的数列。

以下$M$行，每行一条命令，格式参见问题描述中的表格。

输出

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

提示

初始时，我们拥有数列：2 -6 3 5 1 -5 -3 6 3

执行操作GET-SUM 5 4，表示求出数列中从第5个数开始连续4个数字之和，为1+(-5)+(-3)+6 = -1

执行操作MAX-SUM，表示要求求出当前数列中最大的一段和，为3+5+1+(-5)+(-3)+6+3 = 10

执行操作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个数字，即最后一个

执行操作MAKE-SAME 3 3 2，表示从第3个数开始的3个数字，统一修改为2，数列变为：
2 -6 2 2 2 -5 -3 6 -5 7 2

执行操作REVERSE 3 6，表示取出数列中从第3个数开始的连续6个数：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。

【评分方法】

本题设有部分分，对于每一个测试点：

  • 如果你的程序能在输出文件正确的位置上打印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。