维护数列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

4068-1

Input

输入文件的第 1 行包含两个数 N 和 M,N 表示初始时数列中数的个数,M 表示要进行的操作数目。

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

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

Output

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

Sample Input

98 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

Sample Output

-1
10
1
10

Hint

4068-2

 

【数据规模和约定】

你可以认为在任何时刻,数列中至少有 1 个数。

输入数据一定是正确的,即指定位置的数在数列中一定存在。

 

50%的数据中,任何时刻数列中最多含有 30 000 个数;

100%的数据中,任何时刻数列中最多含有 500 000 个数。

 

100%的数据中,任何时刻数列中任何一个数字均在[-1 000, 1 000]内。

100%的数据中,M ≤20 000,插入的数字总数不超过 4 000 000 个,输入文件 大小不超过 20MBytes。

Source

NOI 2005 Day1