NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
108 . 區間加值、區間求和
TopCoder
Tags
Description
給定一個長度為 $N$ 的序列 $a_1, a_2, \ldots, a_N$，以及 $Q$ 筆操作。操作格式如下：
- $1 \ L \ R \ d$：把 $a_L, a_{L + 1}, \ldots, a_R$ 加上 $d$。
- $2 \ L \ R$：詢問 $a_L, a_{L + 1}, \ldots, a_R$ 的總和。
一些提示：
- 這題的數字總和，以及經過操作後的 $a_i$ 的數值是有可能會超過 32-bit 的整數。
- 運算的過程也有可能會不小心溢位喔。
- 可以想想加法的懶人標記要怎麼設計。
- 子任務其實是「單點加值、區間求和」喔。
Input Format
輸入的第一行包含兩個正整數 $N, Q$，分別代表序列的長度，以及操作的數量。
接下來的一行，包含 $N$ 個以空白隔開的整數 $a_1, a_2, \ldots, a_N$。
接下來的 $Q$ 行，每行代表一個操作，操作格式如下：
- $1 \ L \ R \ d$：把 $a_L, a_{L + 1}, \ldots, a_R$ 加上 $d$。
- $2 \ L \ R$：詢問 $a_L, a_{L + 1}, \ldots, a_R$ 的總和。
資料滿足：
- $1 \leq N, Q \leq 2 \times 10^ 5$
- $1 \leq L \leq R \leq N$
- $1 \leq a_i, d \leq 10^ 5$
Output Format
對於每個形如 $2 \ L \ R$ 的操作，輸出 $a_L, a_{L + 1}, \ldots, a_R$ 的總和於一行。
Sample Input 1
5 4
32 4 1 8 2
2 2 4
1 3 3 63
2 1 5
2 2 5
32 4 1 8 2
2 2 4
1 3 3 63
2 1 5
2 2 5
Sample Output 1
13
110
78
110
78
Sample Input 2
6 8
3 1 4 1 5 9
1 2 4 5
2 1 3
1 1 5 6
1 3 6 2
2 1 6
2 2 5
1 2 2 3
2 3 4
3 1 4 1 5 9
1 2 4 5
2 1 3
1 1 5 6
1 3 6 2
2 1 6
2 2 5
1 2 2 3
2 3 4
Sample Output 2
18
76
56
31
76
56
31
Hints
Problem Source
IOICamp 2023 Day2 pH
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 0, 2~7 | 在 1 L R d 的操作中，$L = R$ |
50 |
| 3 | 0~13 | 無特別限制。 | 50 |