E - 商店街の売上調査 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、商店街に並ぶ N 軒の店舗の売上を管理しています。店舗は左から順に 1 番から N 番まで番号が付けられており、店舗 i の初期の月間売上は V_i 円です。はじめ、すべての店舗は営業中です。

高橋君は Q 回の操作を順番に行います。各操作は以下の 3 種類のいずれかです。

  • 操作 1（1 l r x）：季節キャンペーンにより、店舗 l 番から r 番までの営業中のすべての店舗の売上を x 円だけ増加させる。この範囲に閉店済みの店舗が含まれていても、その店舗の売上は変化しない。
  • 操作 2（2 p）：店舗 p 番が閉店する。閉店した店舗の売上はその時点での値で確定する（操作 2 自体は売上の値を変化させない）。閉店した店舗は、以降の操作 1 による売上増加の影響を受けない。なお、店舗 p はこの操作の時点で営業中であることが保証される。
  • 操作 3（3 k）：以下の手順で値を求め、出力する。
  1. 現在営業中の店舗を番号の小さい順に並べたとき、k 番目の店舗の番号を j とする。
  2. 店舗 1 番から店舗 j 番までの中で、既に閉店している店舗をすべて集める。
  3. それらの閉店済み店舗それぞれについて、閉店した時点での売上（操作 2 が行われた時点の売上）を求め、その合計を出力する。該当する閉店済み店舗が 1 つもない場合は 0 を出力する。

この合計値を「累積閉店売上額」と呼ぶ。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 0 \leq V_i \leq 10^9（1 \leq i \leq N）
  • 操作 1 において、1 \leq l \leq r \leq N、1 \leq x \leq 10^4
  • 操作 2 において、1 \leq p \leq N、かつ店舗 p はその時点で営業中である
  • 操作 3 において、1 \leq k \leq (その時点で営業中の店舗の数)（特に、操作 3 が与えられる時点で営業中の店舗が 1 つ以上存在する）
  • 入力はすべて整数である
  • 出力すべき値は 2^{63} 未満であることが保証される（64 ビット符号付き整数に収まる）

入力

N Q
V_1 V_2 \ldots V_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • 1 行目には、店舗の数 N と操作の回数 Q がスペース区切りで与えられる。
  • 2 行目には、各店舗の初期売上 V_1, V_2, \ldots, V_N がスペース区切りで与えられる。
  • 3 行目から Q 行にわたって、各操作が 1 行ずつ与えられる。各操作は以下の形式である。
  • 操作 1 の場合：1 l r x（店舗 l 番から r 番の営業中の店舗の売上を x 円増加させる）
  • 操作 2 の場合：2 p（店舗 p 番を閉店させる）
  • 操作 3 の場合：3 k（営業中の店舗のうち左から k 番目の店舗の番号 j を求め、店舗 1 番から j 番までの累積閉店売上額を出力する）

出力

操作 3 が与えられるたびに、対応する累積閉店売上額を 1 行に出力せよ。

入力例 1

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

出力例 1

0
0
70
90

入力例 2

4 7
0 5 10 15
1 1 4 3
2 1
3 1
2 4
1 2 4 2
3 2
3 1

出力例 2

3
3
3

入力例 3

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

出力例 3

410
1130
110
1055
1775
325
1990

入力例 4

20 35
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
1 1 20 100
2 10
2 1
3 1
1 5 15 50
2 7
3 6
1 1 8 10
2 8
3 5
2 20
1 10 20 200
3 12
2 15
3 10
1 1 20 1
2 2
2 3
3 1
1 4 12 30
2 12
3 7
2 4
2 5
3 1
1 1 20 9999
2 19
3 8
2 6
3 1
2 9
2 11
3 3
1 13 18 123
3 5

出力例 4

105
290
105
640
640
352
1328
729
2130
11334
33010
33010

入力例 5

1 4
1000000000
3 1
1 1 1 10000
3 1
2 1

出力例 5

0
0

Score : 466 pts

Problem Statement

Takahashi manages the sales of N stores lined up in a shopping street. The stores are numbered from 1 to N from left to right, and the initial monthly sales of store i is V_i yen. Initially, all stores are open.

Takahashi performs Q operations in order. Each operation is one of the following 3 types:

  • Operation 1 (1 l r x): Due to a seasonal campaign, increase the sales of all open stores from store l to store r by x yen. Even if closed stores are included in this range, their sales do not change.
  • Operation 2 (2 p): Store p closes. The sales of a closed store are finalized at the value at that point in time (Operation 2 itself does not change the sales value). A closed store is not affected by sales increases from subsequent Operation 1s. It is guaranteed that store p is open at the time of this operation.
  • Operation 3 (3 k): Determine and output a value according to the following procedure:
  1. When the currently open stores are listed in increasing order of their numbers, let j be the number of the k-th store.
  2. Among stores from store 1 to store j, collect all stores that have already closed.
  3. For each of those closed stores, determine the sales at the time of closure (the sales at the time Operation 2 was performed on it), and output the total. If there are no such closed stores, output 0.

This total is called the "cumulative closed sales amount."

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 0 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • For Operation 1: 1 \leq l \leq r \leq N, 1 \leq x \leq 10^4
  • For Operation 2: 1 \leq p \leq N, and store p is open at that time
  • For Operation 3: 1 \leq k \leq (the number of currently open stores) (in particular, at least one store is open when Operation 3 is given)
  • All input values are integers
  • It is guaranteed that the values to be output are less than 2^{63} (they fit in a 64-bit signed integer)

Input

N Q
V_1 V_2 \ldots V_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
  • The first line contains the number of stores N and the number of operations Q, separated by a space.
  • The second line contains the initial sales V_1, V_2, \ldots, V_N of each store, separated by spaces.
  • The following Q lines each contain one operation. Each operation is in the following format:
  • For Operation 1: 1 l r x (increase the sales of open stores from store l to store r by x yen)
  • For Operation 2: 2 p (close store p)
  • For Operation 3: 3 k (find the number j of the k-th store among open stores from the left, and output the cumulative closed sales amount from store 1 to store j)

Output

Each time Operation 3 is given, output the corresponding cumulative closed sales amount on one line.

Sample Input 1

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

Sample Output 1

0
0
70
90

Sample Input 2

4 7
0 5 10 15
1 1 4 3
2 1
3 1
2 4
1 2 4 2
3 2
3 1

Sample Output 2

3
3
3

Sample Input 3

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

Sample Output 3

410
1130
110
1055
1775
325
1990

Sample Input 4

20 35
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100
1 1 20 100
2 10
2 1
3 1
1 5 15 50
2 7
3 6
1 1 8 10
2 8
3 5
2 20
1 10 20 200
3 12
2 15
3 10
1 1 20 1
2 2
2 3
3 1
1 4 12 30
2 12
3 7
2 4
2 5
3 1
1 1 20 9999
2 19
3 8
2 6
3 1
2 9
2 11
3 3
1 13 18 123
3 5

Sample Output 4

105
290
105
640
640
352
1328
729
2130
11334
33010
33010

Sample Input 5

1 4
1000000000
3 1
1 1 1 10000
3 1
2 1

Sample Output 5

0
0