AT_abc363_g [ABC363G] Dynamic Scheduling

题目描述

给定长度为 $N$ 的数列 $D=(D_1,\ D_2,\ \dots,\ D_N),\ P=(P_1,\ P_2,\ \dots,\ P_N)$。

请按顺序处理 $Q$ 个查询。每个查询的格式如下：

• c x y ：将 $D_c$ 改为 $x$，将 $P_c$ 改为 $y$。然后，解决以下问题并输出答案。

有 $N$ 个编号为 $1$ 到 $N$ 的工作。
你从今天（记为第 $1$ 天）开始，每天可以选择 $1$ 个工作完成，连续进行 $N$ 天。
如果在第 $D_i$ 天之前（含第 $D_i$ 天）完成第 $i$ 个工作，可以获得 $P_i$ 的报酬。（如果没有在 $D_i$ 天之前完成，则没有报酬）
请你选择完成工作的顺序，使得可以获得的报酬总和最大，并输出该最大值。

输入格式

输入按以下格式从标准输入给出。这里 $\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

输入 #1

3 2
1 2 3
3 6 3
3 1 4
2 3 9

输出 #1

10
13

输入输出样例 #2

输入 #2

5 1
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1000000000

输出 #2

5000000000

输入输出样例 #3

输入 #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

说明/提示

数据范围

• $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$
• 输入的所有值均为整数

样例解释 1

第 $1$ 个查询如下：

• 将 $D_3$ 改为 $1$，$P_3$ 改为 $4$。此时 $D = (1, 2, 1),\ P = (3, 6, 4)$。
• 在子问题中，按如下顺序完成工作是最优方案之一：第 $1$ 天做工作 $3$，第 $2$ 天做工作 $2$，第 $3$ 天做工作 $1$，此时报酬总和为 $10$，因此输出 $10$。

第 $2$ 个查询如下：

• 将 $D_2$ 改为 $3$，$P_2$ 改为 $9$。此时 $D = (1, 3, 1),\ P = (3, 9, 4)$。
• 在子问题中，按如下顺序完成工作是最优方案之一：第 $1$ 天做工作 $3$，第 $2$ 天做工作 $1$，第 $3$ 天做工作 $2$，此时报酬总和为 $13$，因此输出 $13$。

由 ChatGPT 4.1 翻译