← 返回题目列表

AtCoder · abc363_g

G. 动态调度

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

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