C - Piggy Bank Management Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 個の貯金箱を管理しています。それぞれの貯金箱には 1 から N までの番号が付けられています。

各貯金箱 i（1 \leq i \leq N）には、初期状態で A_i 円が入っています。これから Q 回の操作が順番に行われます。各操作は以下の 2 種類のいずれかです：

  • 種類 1（入金）：正の整数 L, R, X が与えられる。貯金箱 L, L+1, \ldots, R のそれぞれに X 円ずつ入金する。すなわち、これらの貯金箱の金額がそれぞれ X 円増加する。
  • 種類 2（確認）：整数 P が与えられる。貯金箱 P の現在の金額を確認する。

高橋君のために、種類 2 の操作が行われるたびに、その時点で貯金箱 P に入っている金額を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 種類 1 の操作において、1 \leq L \leq R \leq N
  • 種類 1 の操作において、1 \leq X \leq 10^4
  • 種類 2 の操作において、1 \leq P \leq N
  • 種類 2 の操作は 1 回以上存在する
  • 入力はすべて整数
  • 種類 2 の操作における答え（出力する金額）は 10^{18} 以下であることが保証される

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
query_1
query_2
\vdots
query_Q
  • 1 行目には、貯金箱の個数 N と操作の回数 Q が、スペース区切りで与えられる。
  • 2 行目には、各貯金箱の初期金額 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く Q 行にわたって、各操作の情報 query_1, query_2, \ldots, query_Q が 1 行ずつ与えられる。各 query_i は先頭の整数が操作の種類を表し、以下のいずれかの形式である。
  • 種類 1 の場合：1 L R X（貯金箱 L から R までのそれぞれに X 円入金する）
  • 種類 2 の場合：2 P（貯金箱 P の金額を確認する）

出力

種類 2 の操作が行われるたびに、その時点で貯金箱 P に入っている金額を 1 行に出力せよ。

入力例 1

5 4
10 20 30 40 50
2 3
1 2 4 5
2 3
2 1

出力例 1

30
35
10

入力例 2

8 7
100 200 300 400 500 600 700 800
1 1 5 10
1 3 8 20
2 3
2 6
1 1 8 100
2 1
2 8

出力例 2

330
620
210
920

入力例 3

10 10
0 1000000000 500 0 999999999 1 2 3 4 5
1 1 10 10000
2 2
1 5 5 3
2 5
1 1 1 1
2 1
1 3 7 100
2 4
2 10
2 7

出力例 3

1000010000
1000010002
10001
10100
10005
10102

Score : 366 pts

Problem Statement

Takahashi manages N piggy banks. Each piggy bank is numbered from 1 to N.

Each piggy bank i (1 \leq i \leq N) initially contains A_i yen. From now on, Q operations will be performed in order. Each operation is one of the following two types:

  • Type 1 (deposit): Positive integers L, R, X are given. Deposit X yen into each of the piggy banks L, L+1, \ldots, R. That is, the amount in each of these piggy banks increases by X yen.
  • Type 2 (check): An integer P is given. Check the current amount in piggy bank P.

For each Type 2 operation, determine the amount of money currently in piggy bank P.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • For Type 1 operations, 1 \leq L \leq R \leq N
  • For Type 1 operations, 1 \leq X \leq 10^4
  • For Type 2 operations, 1 \leq P \leq N
  • There is at least one Type 2 operation
  • All input values are integers
  • It is guaranteed that the answer for each Type 2 operation (the amount to output) is at most 10^{18}

Input

Input is given from standard input in the following format.

N Q
A_1 A_2 \ldots A_N
query_1
query_2
\vdots
query_Q
  • The first line contains the number of piggy banks N and the number of operations Q, separated by a space.
  • The second line contains the initial amounts A_1, A_2, \ldots, A_N in each piggy bank, separated by spaces.
  • The following Q lines each contain the information for one operation query_1, query_2, \ldots, query_Q. The leading integer of each query_i indicates the type of operation, and the format is one of the following:
  • Type 1: 1 L R X (deposit X yen into each piggy bank from L to R)
  • Type 2: 2 P (check the amount in piggy bank P)

Output

For each Type 2 operation, output the amount of money currently in piggy bank P on a single line.

Sample Input 1

5 4
10 20 30 40 50
2 3
1 2 4 5
2 3
2 1

Sample Output 1

30
35
10

Sample Input 2

8 7
100 200 300 400 500 600 700 800
1 1 5 10
1 3 8 20
2 3
2 6
1 1 8 100
2 1
2 8

Sample Output 2

330
620
210
920

Sample Input 3

10 10
0 1000000000 500 0 999999999 1 2 3 4 5
1 1 10 10000
2 2
1 5 5 3
2 5
1 1 1 1
2 1
1 3 7 100
2 4
2 10
2 7

Sample Output 3

1000010000
1000010002
10001
10100
10005
10102