Problem : 92 - 最大連續和

Problem Statistics

Solved Member: 24　　Submission: 266　　User Tried: 28

Statement:

自從kannaduki被最大子矩陣電的滾來滾去之後，它決定從簡單一維的最大連續和來開始學習。所謂的最大連續和是指一個陣列當中，連續且和最大的一段數字，例如 1,-1,-3,4,5,6 的最大連續和為15(為4,5,6三個數字)。

瀚瀚丟了一題簡單的例題給了kannaduki，沒想到他還是被電的滾來滾去，請你幫幫他。

以下是問題的敘述：

請寫一個「複雜版的最大連續和」，來支持下面的6種指令。

下面有6個指令的格式，你可以假設指令之間以空行分隔，單條指令裡面的數字以空白分隔：

1.插入 - 把 k 個數字 C1, C2, C3, ... , Ck 插入在第 p 個數字的後面。
語法：INSERT p k C1 C2 C3 ... Ck

2.刪除 - 從第 p 個數字開始連續刪除 k 個數字
語法：DELETE p k

3.修改 - 把 p 開始的連續 k 個數字都改成 l
語法：MAKE-SAME p k l

4.反轉 - 把 p 開始的連續 k 個數字倒轉
語法：REVERSE p k

5.求和 - 計算從 p 開始的 k 個數字的和
語法：GET-SUM p k

6.求最大連續和 - 計算目前整個數列中最大的連續和
語法：MAX-SUM

Input:Output:

輸入第 1 行有兩個整數 N,M，分別代表數列最初的數字個數以及有 M 條指令。
第 2 行有 N 個整數，代表剛開始的數列。
接下來 M 行，每行為單一條指令。

M ≤ 20000
你可以假設任何時候，數列最多只會有 500000 個數字，並且每個數字皆在[-1000,1000]之間。
並且所有指令插入的數字總數小於或等於 400萬個。

請對每一個 GET-SUM 指令以及 MAX-SUM 指令輸出一行整數，代表指令輸出的值。

Sample Input:Sample Output:

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

HINT:

以下說明8條指令的動作：

0 - 初始序列

1 - 第5~9個數字和

2 - 最大連續和

3 - 插入3個數字

4 - 刪除第12個數字

5 - 把第3~5個數字改成2

6 - 把第3~8個數字反過來

7&8 - 執行最大和以及第5~8個數字的和

Source:

NOI 2005

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	10000ms	262144kb
1	10000ms	262144kb	10
2	10000ms	262144kb	10
3	10000ms	262144kb	10
4	10000ms	262144kb	10
5	10000ms	262144kb	10
6	10000ms	262144kb	10
7	10000ms	262144kb	10
8	10000ms	262144kb	10
9	10000ms	262144kb	10
10	10000ms	262144kb	10