#P2710. 数列

数列

题目描述

维护一个数列,共 77 种操作:

I. INSERT x n a1 a2 .. an 在第 xx 个数后插入 nn 个数分别为 a1ana_1\dots a_n

II. DELETE x n 删除第 xx 个数开始的 nn 个数。

III. REVERSE x n 翻转第 xx 个数开始的 nn 个数的区间。

IV. MAKE-SAME x n t 将第 xx 个数开始的 nn 个数统一改为 tt

V. GET-SUM x n 输出第 xx 个数开始的 nn 个数的和。

VI. GET x 输出第 xx 个数的值。

VII. MAX-SUM x n 输出第 xx 个数开始的 nn 个数的最大连续子序列和。

输入格式

第一行为 NNMMNN 表示初始序列中数的个数,MM 表示操作的个数。

第二行为 NN 个数 A1AnA_1\dots A_n,表示初始序列。

第三行到第 M+2M+2 行,每行一个操作。

输出格式

输出每个GET-SUMGETMAX-SUM操作的结果。

9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM 1 9
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET 5
MAX-SUM 1 11
-1
10
-5
10

提示

2020 组数据,每组数据随机生成,
保证每个时刻数列里的数不超过 200000200000 个,
任何一个输入的数字均在 10001000-1000\sim1000之间,结果不超过 2302^{30}

121\sim21N5\quad1\le N\le 51M101\le M\le 10

343\sim41N10\quad1\le N\le 101M201\le M\le 20

565\sim61N20\quad1\le N \le 201M501\le M\le 50

787\sim81N50\quad1\le N\le 501M1001\le M\le 100

9109\sim101N100\quad1\le N\le 1001M5001\le M\le 500

111211\sim121N1000\quad 1\le N\le 10001M10001\le M\le 1000

131413\sim141N5000\quad1\le N\le 50001M20001\le M\le 2000

151615\sim161N104\quad1\le N\le 10^41M50001\le M\le 5000

171817\sim181N105\quad1\le N\le 10^51M1041\le M\le 10^4

192019\sim201N2×105\quad1\le N\le 2\times 10^51M2×1041\le M\le 2\times 10^4