CF1179C Serge and Dining Room

Serge 来到学校食堂，发现这里排着一条长队。队伍中有 $m$ 个学生。他现在还不确定是否要等到队伍散去，所以他想知道如果他等到最后，他会拿到哪道菜。由于 Serge 非常疲惫，他让你帮他计算这个问题。 最初有 $n$ 道菜，每道菜的价格分别为 $a_1, a_2, \ldots, a_n$。如你所知，队伍中有 $m$ 个学生，他们分别拥有 $b_1, \ldots, b_m$ 个托格罗（学生按排队顺序编号，即第一个学生拥有 $b_1$ 个托格罗，最后一个学生拥有 $b_m$ 个托格罗）。 学生们认为最贵的菜就是最美味的，所以每个学生都会购买他能买得起的最贵的菜（每道菜只有一份，被买走后其他人就不能再买了）。如果某个学生买不起任何一道菜，他就会离开队伍（真是残酷的资本主义……） 但对 Serge 来说，钱根本不是问题，所以只要还有剩下的菜，他就会买下最贵的那一道。 此外，Serge 的学校经济形势非常不稳定，有些菜的价格或某些学生的托格罗数量可能会发生变化。更正式地说，你需要处理 $q$ 个操作： - 将 $a_i$ 改为 $x$，即第 $i$ 道菜的价格变为 $x$ 个托格罗。 - 将 $b_i$ 改为 $x$，即队伍中第 $i$ 个学生现在拥有 $x$ 个托格罗。 在这些操作期间，没有学生会离开队伍，因为售货员迟到了。 每次操作后，你都需要告诉 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}$），表示每道菜的价格。 第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$（$1 \leq b_i \leq 10^{6}$），表示每个学生拥有的托格罗数量。 第四行包含一个整数 $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$。 - 如果操作是修改某个学生的托格罗数量，格式为 $2\ i\ x$（$1 \leq i \leq m$，$1 \leq x \leq 10^{6}$），表示将 $b_i$ 变为 $x$。

对于每个操作，输出一行答案，表示 Serge 最终会买到的菜的价格，或者如果没有剩下的菜则输出 $-1$。

在第一个样例中，第一次操作后，有一道价格为 $100$ 托格罗的菜和一个只有 $1$ 托格罗的学生，所以 Serge 会买到价格为 $100$ 的菜。 在第二个样例中，第一次操作后，有一道价格为 $1$ 托格罗的菜和一个拥有 $100$ 托格罗的学生，所以 Serge 什么也得不到。 在第三个样例中，没有人能买价格为 $8$ 的菜，所以 Serge 会拿走它。第二次操作后，所有菜都被买走了。第三次操作后，第三和第五个学生分别买走了第一和第二道菜，第四道菜没人买。 由 ChatGPT 4.1 翻译