E - Warehouse Inventory Management Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は N 個の倉庫の在庫管理を担当しています。

倉庫 i（1 \leq i \leq N）には現在 A_i 個の商品が保管されており、今後の注文で必要になる商品の数は B_i 個と見込まれています。

これから Q 件の報告が順に届きます。j 番目（1 \leq j \leq Q）の報告は、種類 T_j、区間の左端 L_j、右端 R_j、個数 X_j からなり、次のいずれかの処理を行います。

  • T_j = 1 のとき：新たな注文が入り、L_j \leq i \leq R_j を満たす各倉庫 i について B_i を X_j 増やす。
  • T_j = 2 のとき：追加の入荷があり、L_j \leq i \leq R_j を満たす各倉庫 i について A_i を X_j 増やす。

各報告による変更は累積的です。すなわち、j 番目の報告はそれ以前の報告による変更が反映された後の A_i, B_i に対して適用されます。

各報告を処理した直後に、全倉庫の不足分の合計を求めてください。ここで、倉庫 i の不足分は \max(0,\ B_i - A_i) と定義します。すなわち、\displaystyle\sum_{i=1}^{N} \max(0,\ B_i - A_i) を出力してください。

制約

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq Q \leq 5 \times 10^4
  • 0 \leq A_i \leq 10^7（1 \leq i \leq N）
  • 0 \leq B_i \leq 10^7（1 \leq i \leq N）
  • T_j \in \{1, 2\}（1 \leq j \leq Q）
  • 1 \leq L_j \leq R_j \leq N（1 \leq j \leq Q）
  • 1 \leq X_j \leq 10^7（1 \leq j \leq Q）
  • 入力はすべて整数である
  • 各出力値は 10^{18} 以下である

入力

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
T_1 L_1 R_1 X_1
T_2 L_2 R_2 X_2
\vdots
T_Q L_Q R_Q X_Q
  • 1 行目には、倉庫の数 N と報告の数 Q がスペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、倉庫 i の現在の商品数 A_i と必要見込み数 B_i がスペース区切りで与えられる。
  • 続く Q 行のうち j 行目（1 \leq j \leq Q）には、j 番目の報告を表す T_j、L_j、R_j、X_j がスペース区切りで与えられる。

出力

S_1
S_2
\vdots
S_Q

Q 行出力してください。

j 行目には、j 番目の報告を処理した直後における全倉庫の不足分の合計 S_j を整数で出力してください。

入力例 1

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

出力例 1

5
5
6
3

入力例 2

5 6
8 1
2 5
0 0
7 7
3 10
2 1 5 2
1 2 4 4
1 5 5 1
2 3 3 10
1 1 5 3
2 2 5 5

出力例 2

6
14
15
13
22
7

入力例 3

8 10
5 3
0 4
10 10
7 12
3 1
6 9
2 8
15 5
1 2 5 3
2 4 7 4
1 1 8 2
2 1 3 5
1 6 8 7
2 8 8 10
1 3 3 6
2 2 6 2
1 1 1 10
2 1 8 1

出力例 3

28
16
25
15
29
29
35
27
32
26

入力例 4

20 25
0 0
5 10
20 5
7 7
12 30
100 80
3 25
40 40
15 0
9 14
60 100
2 1
33 50
25 20
0 45
70 10
6 6
18 35
90 120
11 3
1 1 10 5
2 5 15 12
1 7 20 8
2 1 4 20
1 3 3 50
2 11 20 7
1 12 18 15
2 8 13 30
1 1 20 2
2 15 15 60
1 5 9 25
2 2 6 10
1 14 20 40
2 1 20 3
1 10 10 100
2 10 12 50
1 1 1 10000000
2 1 1 9999999
1 16 19 6
2 18 20 20
1 4 17 9
2 7 7 100
1 6 11 13
2 3 19 4
1 20 20 100

出力例 4

234
159
222
202
222
180
243
183
199
148
198
178
404
376
451
401
10000385
401
420
360
427
371
408
362
462

入力例 5

1 1
0 10000000
2 1 1 10000000

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is in charge of managing the inventory of N warehouses.

Warehouse i (1 \leq i \leq N) currently stores A_i items, and the number of items expected to be needed for future orders is B_i.

Now, Q reports will arrive in order. The j-th (1 \leq j \leq Q) report consists of a type T_j, the left end of the interval L_j, the right end R_j, and a quantity X_j, and performs one of the following operations:

  • When T_j = 1: A new order is placed, and B_i is increased by X_j for each warehouse i satisfying L_j \leq i \leq R_j.
  • When T_j = 2: An additional delivery arrives, and A_i is increased by X_j for each warehouse i satisfying L_j \leq i \leq R_j.

The modifications from each report are cumulative. That is, the j-th report is applied to A_i and B_i after reflecting the changes from all previous reports.

Immediately after processing each report, find the sum of the shortages of all warehouses. Here, the shortage of warehouse i is defined as \max(0,\ B_i - A_i). That is, print \displaystyle\sum_{i=1}^{N} \max(0,\ B_i - A_i).

Constraints

  • 1 \leq N \leq 5 \times 10^4
  • 1 \leq Q \leq 5 \times 10^4
  • 0 \leq A_i \leq 10^7 (1 \leq i \leq N)
  • 0 \leq B_i \leq 10^7 (1 \leq i \leq N)
  • T_j \in \{1, 2\} (1 \leq j \leq Q)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 1 \leq X_j \leq 10^7 (1 \leq j \leq Q)
  • All input values are integers.
  • Each output value is at most 10^{18}.

Input

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
T_1 L_1 R_1 X_1
T_2 L_2 R_2 X_2
\vdots
T_Q L_Q R_Q X_Q
  • The first line contains the number of warehouses N and the number of reports Q, separated by a space.
  • The i-th of the next N lines (1 \leq i \leq N) contains the current number of items A_i and the expected number of needed items B_i of warehouse i, separated by a space.
  • The j-th of the next Q lines (1 \leq j \leq Q) contains T_j, L_j, R_j, and X_j representing the j-th report, separated by spaces.

Output

S_1
S_2
\vdots
S_Q

Print Q lines.

The j-th line should contain the integer S_j, the sum of the shortages of all warehouses immediately after processing the j-th report.

Sample Input 1

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

Sample Output 1

5
5
6
3

Sample Input 2

5 6
8 1
2 5
0 0
7 7
3 10
2 1 5 2
1 2 4 4
1 5 5 1
2 3 3 10
1 1 5 3
2 2 5 5

Sample Output 2

6
14
15
13
22
7

Sample Input 3

8 10
5 3
0 4
10 10
7 12
3 1
6 9
2 8
15 5
1 2 5 3
2 4 7 4
1 1 8 2
2 1 3 5
1 6 8 7
2 8 8 10
1 3 3 6
2 2 6 2
1 1 1 10
2 1 8 1

Sample Output 3

28
16
25
15
29
29
35
27
32
26

Sample Input 4

20 25
0 0
5 10
20 5
7 7
12 30
100 80
3 25
40 40
15 0
9 14
60 100
2 1
33 50
25 20
0 45
70 10
6 6
18 35
90 120
11 3
1 1 10 5
2 5 15 12
1 7 20 8
2 1 4 20
1 3 3 50
2 11 20 7
1 12 18 15
2 8 13 30
1 1 20 2
2 15 15 60
1 5 9 25
2 2 6 10
1 14 20 40
2 1 20 3
1 10 10 100
2 10 12 50
1 1 1 10000000
2 1 1 9999999
1 16 19 6
2 18 20 20
1 4 17 9
2 7 7 100
1 6 11 13
2 3 19 4
1 20 20 100

Sample Output 4

234
159
222
202
222
180
243
183
199
148
198
178
404
376
451
401
10000385
401
420
360
427
371
408
362
462

Sample Input 5

1 1
0 10000000
2 1 1 10000000

Sample Output 5

0