#P2042. [NOI2005] 维护数列

[NOI2005] 维护数列

题目描述

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

编号 名称 格式 说明
1 插入 $\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}$ 在当前数列的第 posiposi 个数字后插入 tottot 个数字:c1,c2ctotc_1, c_2 \cdots c_{tot};若在数列首插入,则 posiposi00
2 删除 DELETE posi tot\operatorname{DELETE} \ posi \ tot 从当前数列的第 posiposi 个数字开始连续删除 tottot 个数字
3 修改 MAKE-SAME posi tot c\operatorname{MAKE-SAME} \ posi \ tot \ c 从当前数列的第 posiposi 个数字开始的连续 tottot 个数字统一修改为 cc
4 翻转 REVERSE posi tot\operatorname{REVERSE} \ posi \ tot 取出从当前数列的第 posiposi 个数字开始的 tottot 个数字,翻转后放入原来的位置
5 求和 GET-SUM posi tot\operatorname{GET-SUM} \ posi \ tot 计算从当前数列的第 posiposi 个数字开始的 tottot 个数字的和并输出
6 求最大子列和 MAX-SUM\operatorname{MAX-SUM} 求出当前数列中和最大的一段子列,并输出最大和

输入格式

第一行包含两个整数 NNMMNN 表示初始时数列中数的个数,MM 表示要进行的操作数目。

第二行包含 NN 个数字,描述初始时的数列。以下 MM 行,每行一条命令,格式参见问题描述中的表格。

输出格式

对于输入数据中的 GET-SUM\operatorname{GET-SUM}MAX-SUM\operatorname{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

提示

数据规模与约定

  • 你可以认为在任何时刻,数列中至少有 11 个数。
  • 输入数据一定是正确的,即指定位置的数在数列中一定存在。
  • 对于 50%50\% 的数据,任何时刻数列中最多含有 3×1043 \times 10^4 个数。
  • 对于 100%100\% 的数据,任何时刻数列中最多含有 5×1055 \times 10^5 个数,任何时刻数列中任何一个数字均在 [103,103][-10^3, 10^3] 内,1M2×1041 \le M \le 2 \times 10^4,插入的数字总数不超过 4×1064 \times 10^6

题面由 @syksykCCC 提供。