AT_abc467_f [ABC467F] Email Scheduling Optimization

给定长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$ 和 $B=(B_1,B_2,\dots,B_N)$。 有 $Q$ 个操作。 每个操作有以下两种类型之一： - `1 i x`：将 $A_i$ 改为 $x$。 - `2 i x`：将 $B_i$ 改为 $x$。 每次处理完一个操作后，需要解决以下问题： > Takahashi 需要给 $N$ 家公司每家发送一封邮件，并收到每家的回复。 > 写给第 $j$ 家公司的邮件需要 $A_j$ 分钟，收到回复需要在邮件发送后 $B_j$ 分钟。 > 他从时间 $0$ 开始写邮件， > 可以以任意顺序书写这 $N$ 封邮件，但不能同时书写多封邮件。 > 请你求出，他最早能收到所有公司的回复的最小可能时间。 > 可以假设发送邮件花费的时间可以忽略不计。

输入通过标准输入给出，格式如下： > $N\ Q\ A_1\ A_2\ \cdots\ A_N\ B_1\ B_2\ \cdots\ B_N\ \mathrm{query}_1\ \mathrm{query}_2\ \vdots\ \mathrm{query}_Q$ 对于每个操作 $\mathrm{query}_q$，以空格分隔依次给出操作类型（$1$ 或 $2$）、$i$、$x$。 也就是每个操作以如下两种格式之一给出： > $1\ i\ x$ > $2\ i\ x$

共输出 $Q$ 行。第 $q$ 行输出处理完第 $q$ 个操作后的答案。

### 样例解释 1 处理完第一个操作后，$A=(4,1,7)$，$B=(4,6,7)$。 如果 Takahashi 先从公司 $3$ 开始写邮件，$0$ 时刻开始，$7$ 分钟写完，邮件送达公司 $3$，$14$ 时刻收到回复。 接着 $7$ 时刻开始写公司 $2$，写 $1$ 分钟，$8$ 时刻完成，$14$ 时刻收到回复。 最后 $8$ 时刻开始写公司 $1$，写 $4$ 分钟，$12$ 时刻完成，$16$ 时刻收到回复。 ### 数据范围 - $1\leq N\leq 10^5$ - $1\leq Q\leq 10^5$ - $1\leq A_j,B_j\leq 10^9$ - 对于每个操作，$1\leq i\leq N$ - 对于每个操作，$1\leq x\leq 10^9$ - 输入均为整数。 由 ChatGPT 5 翻译