← 返回题目列表

AtCoder · awc0104_e

E. 仓库库存管理

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥负责管理库存 N 仓库。

仓库 i (1 \leq i \leq N) 当前存储 A_i 商品,并且未来订单预计需要的商品数量为 B_i.

现在, Q 报告将按顺序送达。的 j-th (1 \leq j \leq Q) 报告由一个类型组成 T_j,区间的左端 L_j,右端 R_j,以及数量 X_j,并执行以下操作之一:

  • 当 T_j = 1: 下达了新订单,并且 B_i 增加 每个仓库的 X_j 对于每个仓库 i 满意 L_j \leq i \leq R_j.
  • 当 T_j = 2:额外的交货到达,并且 A_i 增加 每个仓库的 X_j 对于每个仓库 i 满意 L_j \leq i \leq R_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
  • 第一行包含仓库数量 N 和报告数量 Q,用空格分隔。
  • 的 i- 下一个 N 行 (1 \leq i \leq N) 包含当前项目数 A_i 以及所需物品的预期数量 仓库 B_i 仓库的 i,用空格分隔。
  • 的 j- 下一个 Q 行 (1 \leq j \leq Q) 包含 T_j, L_j, R_j,和 X_j 代表 j第一份报告,以空格分隔。

输出

S_1
S_2
\vdots
S_Q

打印 Q 行。

的 j- 第行应包含整数 S_j,处理完后立即所有仓库的缺货总和 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