CF1477E Nezzar and Tournaments

在著名的 Oh-Suit-United 锦标赛中，两支队伍正在为珍贵的辣椒分大奖展开对决。 第一支队伍有 $n$ 名选手，第二支队伍有 $m$ 名选手。每位选手都有一个潜力值：第一支队伍第 $i$ 名选手的潜力值为 $a_i$，第二支队伍第 $i$ 名选手的潜力值为 $b_i$。 在比赛中，所有选手将以某种顺序依次上场。现场有一个计分装置，初始分数为整数 $k$，用于评估所有选手的表现。 所有选手的得分将按照他们上场的顺序分配。设当前选手的潜力值为 $x$，上一位选手的潜力值为 $y$（对于第一个上场的选手，$y=x$）。那么，$x-y$ 会被加到计分装置的当前值上。如果此时计分装置的值变为负数，则会被重置为 $0$。最后，该选手的得分就是计分装置当前的值。一个队伍的得分为其所有成员得分之和。 作为第一支队伍的狂热粉丝，Nezzar 迫切希望第一支队伍能获得最大的胜利。他现在想知道，第一支队伍与第二支队伍得分的最大差值是多少。 形式化地，设第一支队伍的得分为 $score_f$，第二支队伍的得分为 $score_s$。Nezzar 想要找到所有可能的上场顺序中 $score_f - score_s$ 的最大值。 然而，情况经常发生变化，将会有 $q$ 个事件发生。事件有三种类型： - $1\ pos\ x$ —— 将 $a_{pos}$ 改为 $x$； - $2\ pos\ x$ —— 将 $b_{pos}$ 改为 $x$； - $3\ x$ —— 以 $k=x$ 举办比赛，Nezzar 希望你计算 $score_f - score_s$ 的最大值。 你能帮助 Nezzar 回答所有第三类查询吗？

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n,m \le 2 \cdot 10^5, 1 \le q \le 5 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^6$）。 第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$0 \le b_i \le 10^6$）。 接下来的 $q$ 行，每行描述一个事件，格式如下： - $1\ pos\ x$（$1 \le pos \le n$，$0 \le x \le 10^6$）； - $2\ pos\ x$（$1 \le pos \le m$，$0 \le x \le 10^6$）； - $3\ x$（$0 \le x \le 10^6$）。

对于每个第三类查询，输出该查询的答案。

在第一个测试的第一个查询中，比赛以 $k=5$ 举行。最优的上场顺序如下（括号内为选手的潜力值）： $\underline{7}$，$3$，$5$，$4$，$6$，$\underline{1}$，$\underline{2}$（下划线表示第一支队伍的选手）。 按上场顺序编号，选手的个人得分为： - 第 $\underline{1}$ 位选手：$\max(5 + (7 - 7), 0) = 5$； - 第 $2$ 位选手：$\max(5 + (3 - 7), 0) = 1$； - 第 $3$ 位选手：$\max(1 + (5 - 3), 0) = 3$； - 第 $4$ 位选手：$\max(3 + (4 - 5), 0) = 2$； - 第 $5$ 位选手：$\max(2 + (6 - 4), 0) = 4$； - 第 $\underline{6}$ 位选手：$\max(4 + (1 - 6), 0) = 0$； - 第 $\underline{7}$ 位选手：$\max(0 + (2 - 1), 0) = 1$。 因此，$score_f = 5 + 0 + 1 = 6$，$score_s = 1 + 3 + 2 + 4 = 10$。得分差为 $6 - 10 = -4$。可以证明，这就是最大可能的得分差。 由 ChatGPT 4.1 翻译