动态调度

题目描述

给定两个长度为 $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 天),你将在 $N$ 天中每天选择并完成一个工作。

如果你在第 $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$ 个查询的答案。

样例

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

10
13

第一个查询如下:

将 $D_3$ 改为 $1$,将 $P_3$ 改为 $4$。此时 $D = (1, 2, 1)$,$P = (3, 6, 4)$。

在子问题中,一种最优做法是:第 1 天完成工作 3,第 2 天完成工作 2,第 3 天完成工作 1。总奖励为 $10$,所以输出 $10$。

第二个查询如下:

将 $D_2$ 改为 $3$,将 $P_2$ 改为 $9$。此时 $D = (1, 3, 1)$,$P = (3, 9, 4)$。

在子问题中,一种最优做法是:第 1 天完成工作 3,第 2 天完成工作 1,第 3 天完成工作 2。总奖励为 $13$,所以输出 $13$。

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

5000000000

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

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$
• 所有输入值都是整数。