分数: 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