← 返回题目列表

Codeforces · 1477/E

E. 内扎尔和锦标赛

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

在著名的 Oh-Suit-United 锦标赛中,两支队伍正在为争夺珍贵的胡椒点大奖而展开对决。

第一队由$$$n$$$玩家组成,第二队由$$$m$$$玩家组成。每个球员都有潜力:第一队中第 $$$i$$$ 球员的潜力为 $$$a_i$$$,第二队中第 $$$i$$$ 球员的潜力为 $$$b_i$$$。

比赛中,所有选手将按一定顺序上台。将会有一个计分装置,最初分配给一个整数$$$k$$$,它将用于评估所有玩家的表现。

所有玩家的分数将按照他们在舞台上出现的顺序分配。令当前玩家的潜力为$$$x$$$,前一个玩家的潜力为$$$y$$$($$$y$$$ 等于第一个玩家的$$$x$$$)。然后,将$$$x-y$$$加上计分器中的值,之后,如果计分器中的值变为负数,则该值将被重置为$$$0$$$。最后,玩家的分数被分配给计分设备上的当前值。团队的得分是其所有成员得分的总和。

作为一线队的疯狂球迷,内扎尔迫切希望一线队取得最大的胜利。他现在想知道第一队和第二队的分数最大相差多少。

正式来说,让第一队的得分为$$$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$$$)。

输出

对于第三种类型的每个查询,打印该查询的答案。

示例

输入 #1

3 4 3
1 2 7
3 4 5 6
3 5
1 1 10
3 5

输出 #1

-4
9

输入 #2

7 8 12
958125 14018 215153 35195 90380 30535 204125
591020 930598 252577 333333 999942 1236 9456 82390
3 123458
2 4 444444
3 123456
1 2 355555
3 123478
3 1111
2 6 340324
3 1111
2 8 999999
2 7 595959
3 222222
3 100

输出 #2

1361307
1361311
1702804
1879305
1821765
1078115
1675180

注意

在第一次测试的第一个查询中,锦标赛以 $$$k = 5$$$ 举行。最好这样安排球员(这里写的是他们的潜力):

$$$\underline{7}$$$、$$$3$$$、$$$5$$$、$$$4$$$、$$$6$$$、$$$\underline{1}$$$、$$$\underline{2}$$$(下划线数字是一线队球员的潜力)。

选手个人得分按出场顺序编号为:

- $$$\max(5 + (7 - 7), 0) = 5$$$ 对于 $$$\underline{1}$$$-st 玩家;
- $$$\max(5 + (3 - 7), 0) = 1$$$ 对于第 $$$2$$$ 位玩家;
- $$$\max(1 + (5 - 3), 0) = 3$$$ 对于第 $$$3$$$-rd 玩家;
- 第 $$$4$$$ 位玩家的 $$$\max(3 + (4 - 5), 0) = 2$$$;
- 第 $$$5$$$ 位玩家的 $$$\max(2 + (6 - 4), 0) = 4$$$;
- $$$\max(4 + (1 - 6), 0) = 0$$$ 对于第 $$$\underline{6}$$$ 玩家;
- 第 $$$\underline{7}$$$ 位玩家的 $$$\max(0 + (2 - 1), 0) = 1$$$。

因此,$$$score_f = 5 + 0 + 1 = 6$$$ 和 $$$score_s = 1 + 3 + 2 + 4 = 10$$$。分数差异为 $$$6 - 10 = -4$$$。可以证明,这是最大可能的分数差。