CSES 2166 - Prefix Sum Queries

1.0s 512M

給定一個包含 \(n\) 個整數的陣列，依序處理 \(q\) 個操作，每個操作可能是以下兩種類型之一：

將位置 \(k\) 的值更新為 \(u\)。
求子陣列 \(a[a..b]\) 內的最大前綴和。

允許空前綴（其和為 \(0\)）。

輸入格式

第一行：兩個整數 \(n\) 和 \(q\)（陣列長度與操作數）。
第二行：\(n\) 個整數 \(x_1, x_2, \ldots, x_n\)（陣列初始值）。
接下來 \(q\) 行，每行格式為 1 k u（更新）或 2 a b（查詢）。

輸出格式

對每個第 2 類操作，輸出一個整數，代表答案。

範例輸入 1

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

範例輸出 1

5
2
0

限制

\(1 \le n, q \le 2 \cdot 10^5\)
\(-10^9 \le x_i, u \le 10^9\)
\(1 \le k \le n\)
\(1 \le a \le b \le n\)

題目來源

CSES - Prefix Sum Queries

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。