← 返回题目列表

Codeforces · 1179/C

C. 哔叽和餐厅

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

Serge来到学校食堂,发现这里排着长队。队列中有 $$$m$$$ 名学生。他现在不确定是否要等到队列清空,所以他想知道如果等待,他会收到哪道菜。由于 Serge 很累,他请你代替他来计算。

最初有 $$$n$$$ 菜肴,成本为 $$$a_1、a_2、\ldots、a_n$$$。如您所知,有 $$$m$$$ 学生的队列,分别有 $$$b_1、\ldots、b_m$$$ togrogs(学生按队列顺序枚举,即队列中的第一个学生有 $$$b_1$$$ togrogs,最后一个学生有 $$$b_m$$$ togrogs)

学生认为最贵的菜就是最好吃的,所以每个学生都只买自己有钱的最贵的菜(每道菜都有一份,所以学生买了之后就没有人可以再买了),如果学生没有钱买任何菜,他就离开队列(太残酷的资本主义……)

但钱对 Serge 来说根本不是问题,所以如果至少剩下一道菜,Serge 就会买最贵的菜。

此外,Serge 的学校经济形势非常不稳定,某些学生的某些菜肴的成本或 togrogs 的数量可能会发生变化。更正式地说,您必须处理 $$$q$$$ 查询:

- 将 $$$a_i$$$ 更改为 $$$x$$$。这意味着第 $$$i$$$ 菜的价格变为 $$$x$$$ togrogs。
- 将 $$$b_i$$$ 更改为 $$$x$$$。这意味着队列中第 $$$i$$$ 个学生现在有 $$$x$$$ 的 togrogs。

在这些查询期间,没有人因为售货员迟到而离开队列。

每次查询后,您必须根据上述规则告诉Serge,如果他等到队列清空,他将购买的菜肴的价格,或者如果此时没有菜肴,则为$$$-1$$$。

输入

第一行包含整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 300\ 000$$$) — 分别是菜肴数量和学生数量。第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{6}$$$) — 数组 $$$a$$$ 的元素。第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_{m}$$$ ($$$1 \leq b_i \leq 10^{6}$$$) — 数组 $$$b$$$ 的元素。第四行包含整数 $$$q$$$ ($$$1 \leq q \leq 300\ 000$$$) — 查询数。

以下每行 $$$q$$$ 包含如下内容:

- 如果查询更改了某些菜肴的价格,它包含 $$$1$$$ 和两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^{6}$$$),这意味着 $$$a_i$$$ 变为 $$$x$$$。
- 如果查询更改了某个学生的 togrogs 数量,它包含 $$$2$$$ 和两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i \leq m$$$, $$$1 \leq x \leq 10^{6}$$$),这意味着 $$$b_i$$$ 变为 $$$x$$$。

输出

对于每个 $$$q$$$ 查询,打印语句描述的答案,第 $$$i$$$ 行中第 $$$i$$$ 查询的答案(Serge 将购买的菜肴的价格,如果没有剩余,则为 $$$-1$$$)

示例

输入 #1

1 1
1
1
1
1 1 100

输出 #1

100

输入 #2

1 1
1
1
1
2 1 100

输出 #2

-1

输入 #3

4 6
1 8 2 4
3 3 6 1 5 2
3
1 1 1
2 5 10
1 1 6

输出 #3

8
-1
4

注意

在第一次查询后的第一个样本中,有一个菜品价格为 $$$100$$$ togrogs,而一名学生则有一个 togrogs,因此 Serge 将购买价格为 $$$100$$$ togrogs 的菜品。

在第一次查询后的第二个样本中,有一道菜肴的价格为 1 togrogs,而一名学生的 togrogs 价格为 $$$100$$$,因此 Serge 将一无所获。

在第一次查询后的第三个样本中,没有人可以购买价格为 $$$8$$$ 的菜肴,因此 Serge 将接受它。第二次查询后,所有菜品都会被购买,第三次查询后,第三个和第五个学生将分别购买第一和第二个菜品,而第四个则没有人购买。