P3884 - 【平衡树 NOI2005】维修数列

题目

P3884【平衡树 NOI2005】维修数列

限制 : 时间限制 : - MS 空间限制 : 265536 KB

评测说明 : 1s

问题描述

备注：子序列不能为空

输入格式

第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。

输出格式

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

提示

你可以认为在任何时刻，数列中至少有 1 个数。输入数据一定是正确的，即指定位置的数在数列中一定存在。

50%的数据中，任何时刻数列中最多含有 30 000 个数； 100%的数据中，任何时刻数列中最多含有 500 000 个数。

100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。 100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 个，输入文件大小不超过 20MBytes。