/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は、横一列に並んだ N 個の花壇を管理しています。各花壇には 1 から N までの番号が付けられており、花壇 i には最初 C_i リットルの水が蓄えられています。
高橋君はこれから Q 回の操作を順番に行います。各操作は、前の操作の結果が反映された状態で行われます。操作は以下の 2 種類です。
- 操作 1（水やり）：
1 l r v— 番号が l 以上 r 以下のすべての花壇それぞれに v リットルの水を追加する。 - 操作 2（確認）：
2 l r— 番号が l 以上 r 以下のすべての花壇に蓄えられている水の量の合計値を出力する。
すべての操作 2 に対する答えを、与えられた順に求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 0 \leq C_i \leq 10^4 (1 \leq i \leq N)
- 操作 1 において、1 \leq l \leq r \leq N かつ 1 \leq v \leq 10^4
- 操作 2 において、1 \leq l \leq r \leq N
- 操作 2 は 1 回以上与えられる
- 入力はすべて整数である
- 操作 2 に対する答えは 0 以上 2^{63} - 1（符号付き 64 ビット整数の最大値）以下であることが保証される
入力
N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
各 \text{query}_j (1 \leq j \leq Q) は、以下のいずれかの形式で与えられる。
1 l r v
2 l r
- 1 行目には、花壇の数を表す整数 N と操作回数を表す整数 Q が、スペース区切りで与えられる。
- 2 行目には、各花壇の初期の水の量を表す整数 C_1, C_2, \ldots, C_N が、スペース区切りで与えられる。
- 続く Q 行のそれぞれに、各操作が 1 つずつ与えられる。
- 操作 1 の場合は
1 l r vの形式で、操作の種類、区間の左端 l、区間の右端 r、追加する水の量 v の 4 つの整数がスペース区切りで与えられる。 - 操作 2 の場合は
2 l rの形式で、操作の種類、区間の左端 l、区間の右端 r の 3 つの整数がスペース区切りで与えられる。
出力
操作 2 が与えられるたびに、その時点での番号が l 以上 r 以下の花壇に蓄えられている水の量の合計値を 1 行に出力せよ。出力は操作が与えられた順に行うこと。
入力例 1
5 4 3 1 4 1 5 2 1 5 1 2 4 3 2 2 4 2 1 5
出力例 1
14 15 23
入力例 2
8 7 2 5 3 7 1 4 6 2 2 1 8 1 3 6 2 2 3 6 1 1 4 5 2 2 7 1 5 8 1 2 1 8
出力例 2
30 23 49 62
入力例 3
10 10 10 20 30 40 50 60 70 80 90 100 2 1 10 1 1 5 10 2 1 5 2 6 10 1 3 8 20 2 1 10 1 1 10 5 2 1 10 2 5 5 2 1 1
出力例 3
550 200 400 720 770 85 25
Score : 466 pts
Problem Statement
Takahashi manages N flower beds arranged in a horizontal row. Each flower bed is numbered from 1 to N, and flower bed i initially stores C_i liters of water.
Takahashi will perform Q operations in order. Each operation is performed on the state resulting from all previous operations. There are 2 types of operations:
- Operation 1 (Watering):
1 l r v— Add v liters of water to each flower bed with a number from l to r, inclusive. - Operation 2 (Query):
2 l r— Output the total amount of water stored across all flower beds with numbers from l to r, inclusive.
Find the answers to all operation 2 queries in the order they are given.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 0 \leq C_i \leq 10^4 (1 \leq i \leq N)
- For operation 1, 1 \leq l \leq r \leq N and 1 \leq v \leq 10^4
- For operation 2, 1 \leq l \leq r \leq N
- At least one operation 2 is given
- All input values are integers
- It is guaranteed that the answer to each operation 2 is between 0 and 2^{63} - 1 (the maximum value of a signed 64-bit integer), inclusive
Input
N Q
C_1 C_2 \ldots C_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Each \text{query}_j (1 \leq j \leq Q) is given in one of the following formats:
1 l r v
2 l r
- The first line contains an integer N representing the number of flower beds and an integer Q representing the number of operations, separated by a space.
- The second line contains integers C_1, C_2, \ldots, C_N representing the initial amount of water in each flower bed, separated by spaces.
- Each of the following Q lines contains one operation.
- For operation 1, it is given in the format
1 l r v, consisting of 4 integers separated by spaces: the operation type, the left endpoint l of the range, the right endpoint r of the range, and the amount of water v to add. - For operation 2, it is given in the format
2 l r, consisting of 3 integers separated by spaces: the operation type, the left endpoint l of the range, and the right endpoint r of the range.
Output
Each time an operation 2 is given, output the total amount of water stored in the flower beds with numbers from l to r, inclusive, at that point in time, on a single line. Output the results in the order the operations are given.
Sample Input 1
5 4 3 1 4 1 5 2 1 5 1 2 4 3 2 2 4 2 1 5
Sample Output 1
14 15 23
Sample Input 2
8 7 2 5 3 7 1 4 6 2 2 1 8 1 3 6 2 2 3 6 1 1 4 5 2 2 7 1 5 8 1 2 1 8
Sample Output 2
30 23 49 62
Sample Input 3
10 10 10 20 30 40 50 60 70 80 90 100 2 1 10 1 1 5 10 2 1 5 2 6 10 1 3 8 20 2 1 10 1 1 10 5 2 1 10 2 5 5 2 1 1
Sample Output 3
550 200 400 720 770 85 25