[IOI Camp Judge]區間最大連續和 (題目備份)

IOI Camp Judge是暫時性的，因此在這裡作個題目備份，請大家參考～

題解在這裡

區間最大連續和

Time Limit: 3s

Description

連續和，表示一個序列中連續一段的和。最大連續和代表一個序列中所有連續和的最大值。即對於序列 A1,A2,…,AN，其最大連續和定義爲 max{∑i=lrAi∣∀ l,r s.t. 1≤l≤r≤N}

給你一個序列 A 包含 N 個整數，你要對這個序列做以下五種操作：

• 插入：在序列中第 x 個數之後，插入 k 個相同的數 v
• 刪除：從序列中第 x 個數開始，刪除連續 k 個數
• 修改：從序列中第 x 個數開始，將連續 k 個數修改爲 v
• 求和：求序列中第 x 個數開始，連續 k 個數的和
• 求最大連續和：求當前序列的最大連續和

Input Format

第一行包含一個正整數 T ，代表測試資料筆數。
每筆測試資料第一行包含兩個整數 N,M，代表序列長度以及操作次數。
第二行包含 N 個整數 A1,A2,…,AN，代表最初序列中的數。
接下來共有 M 行，每行包含若干個數字代表一項操作：
若爲 0 x k v：代表插入操作，在第 x 個數之後，插入 k 個相同的數 v
若爲 1 x k$$：代表刪除操作，從第 x 個數開始，刪除連續 k 個數
若爲 2 x k v：代表修改操作，從第 x 個數開始，將連續 k 個數修改爲 v
若爲 3 x k：代表求和操作，求第 x 個數開始，連續 k 個數的和
若爲 4：代表求最大連續和：求當前序列的最大連續和

• 1≤T≤5
• 1≤N,M≤105
• k≥1
• 0≤∣Ai∣,∣v∣≤1000
• 所有測試資料保證，對於每個操作所包含的區間皆爲合法區間，即對於刪除、修改、求和操作，從第 i 個數開始必定包含至少 k 個數
• 所有測試資料保證，插入序列的數字個數總共不會超過 105 個

Output Format

對於每筆求和或求最大連續和操作，輸出相對應的值。

Sample Input

1
5 10
1 -2 3 -4 5
4
0 1 2 3
4
3 3 3
2 3 2 -4
4
0 4 3 1
4
1 3 3
4

Sample Output

5
9
4
5
7
10