题目描述
维护一个数列,共 7 种操作:
I. INSERT x n a1 a2 .. an
在第 x 个数后插入 n 个数分别为 a1…an。
II. DELETE x n
删除第 x 个数开始的 n 个数。
III. REVERSE x n
翻转第 x 个数开始的 n 个数的区间。
IV. MAKE-SAME x n t
将第 x 个数开始的 n 个数统一改为 t。
V. GET-SUM x n
输出第 x 个数开始的 n 个数的和。
VI. GET x
输出第 x 个数的值。
VII. MAX-SUM x n
输出第 x 个数开始的 n 个数的最大连续子序列和。
输入格式
第一行为 N,M,N 表示初始序列中数的个数,M 表示操作的个数。
第二行为 N 个数 A1…An,表示初始序列。
第三行到第 M+2行,每行一个操作。
输出格式
输出每个GET-SUM
,GET
,MAX-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
提示
共 20 组数据,每组数据随机生成,
保证每个时刻数列里的数不超过 200000 个,
任何一个输入的数字均在 −1000∼1000之间,结果不超过 230。
第 1∼2 组 1≤N≤5,1≤M≤10。
第 3∼4 组 1≤N≤10,1≤M≤20。
第 5∼6 组 1≤N≤20,1≤M≤50。
第 7∼8 组 1≤N≤50,1≤M≤100。
第 9∼10 组 1≤N≤100,1≤M≤500。
第 11∼12 组 1≤N≤1000,1≤M≤1000。
第 13∼14 组 1≤N≤5000,1≤M≤2000。
第 15∼16 组 1≤N≤104,1≤M≤5000。
第 17∼18 组 1≤N≤105,1≤M≤104。
第 19∼20 组 1≤N≤2×105,1≤M≤2×104。