CSES 1735 - Range Updates and Sums

1.0s 512M

維護一個長度為 \(n\) 的陣列，要能高效地處理以下三種操作：

將區間 \([a, b]\) 的每個值加上 \(x\)。
將區間 \([a, b]\) 的每個值設為 \(x\)。
計算區間 \([a, b]\) 的元素總和。

輸入格式

第一行：兩個整數 \(n\) 和 \(q\)（陣列長度與操作數）。
第二行：\(n\) 個整數 \(t_1, t_2, \ldots, t_n\)（陣列初始值）。
接下來 \(q\) 行，每行格式為 1 a b x、2 a b x 或 3 a b。

輸出格式

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

範例輸入 1

6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5

範例輸出 1

7
11
15

限制

\(1 \le n, q \le 2 \cdot 10^5\)
\(1 \le t_i, x \le 10^6\)
\(1 \le a \le b \le n\)

題目來源

CSES - Range Updates and Sums

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