分数: 675 点
问题陈述
给定两个长度的序列 N: D=(D_1, D_2, \dots, D_N) 和 P=(P_1, P_2, \dots, P_N).
流程 Q 按给出的顺序进行查询。每个查询均按以下格式给出:
c x y:更改 D_c to x 和 P_c to y。然后,解决以下问题并打印答案。
有 N 职位编号 1 to N.
从今天开始(将此视为一天 1),您每天将选择并完成一项工作 N 天。
如果您完成作业 i 当日或之前 D_i,您将获得奖励 P_i。 (如果您没有在当天完成 D_i,你什么也得不到。)
通过选择完成作业的最佳顺序来找到您可以获得的最大总奖励。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq D_i \leq N
- 1 \leq P_i \leq 10^9
- 1 \leq c \leq N
- 1 \leq x \leq N
- 1 \leq y \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出。在这里, \mathrm{query}_i 表示 i第一个查询。
N Q
D_1 D_2 \dots D_N
P_1 P_2 \dots P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均按以下格式给出。
c x y
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
3 2 1 2 3 3 6 3 3 1 4 2 3 9
示例输出 1
10 13
第一个查询如下:
- 更新 D_3 to 1 和 P_3 to 4。现在, D = (1, 2, 1) 和 P = (3, 6, 4).
- 在子问题中,一个最佳程序是完成作业 3 当天 1,作业 2 当天 2,以及工作 1 当天 3。总奖励为 10,所以打印 10.
第二个查询如下:
- 更新 D_2 to 3 和 P_2 to 9。现在, D = (1, 3, 1) 和 P = (3, 9, 4).
- 在子问题中,一个最佳程序是完成作业 3 当天 1,作业 1 当天 2,以及工作 2 当天 3。总奖励为 13,所以打印 13.
示例输入 2
5 1 1 2 3 4 5 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 1000000000
示例输出 2
5000000000
示例输入 3
10 10 6 2 4 1 5 1 6 6 5 3 45 65 71 52 86 52 48 60 40 98 5 6 5 8 4 34 6 7 83 1 3 21 7 5 85 7 4 51 8 2 81 2 7 54 6 1 5 8 6 30
示例输出 3
394 379 462 457 459 414 443 479 401 396