CF1354D Multiset

注意，本题的内存限制不同于常规题目。 给定一个包含 $n$ 个整数的多重集。你需要处理两种类型的操作： - 向多重集中添加整数 $k$； - 查询并删除多重集中第 $k$ 小的数。 多重集中的第 $k$ 小数，指的是将多重集中的所有元素从小到大排序后，第 $k$ 个元素。例如，如果多重集包含元素 $1$、$4$、$2$、$1$、$4$、$5$、$7$，且 $k=3$，那么排序后为 $[1, 1, 2, 4, 4, 5, 7]$，第 $3$ 小的数是 $2$。如果要删除的元素在多重集中出现多次，仅删除其中一个。 在所有操作完成后，输出多重集中的任意一个数。如果多重集为空，输出 $0$。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^6$），分别表示初始多重集中的元素个数和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_1 \le a_2 \le \dots \le a_n \le n$），表示多重集中的元素。 第三行包含 $q$ 个整数 $k_1, k_2, \ldots, k_q$，每个整数代表一个操作： - 如果 $1 \le k_i \le n$，则第 $i$ 个操作为“将 $k_i$ 插入多重集”； - 如果 $k_i < 0$，则第 $i$ 个操作为“删除多重集中第 $|k_i|$ 小的数”。对于此操作，保证 $|k_i|$ 不大于当前多重集的大小。

如果所有操作后多重集为空，输出 $0$。 否则，输出多重集中任意一个元素。

在第一个样例中，多重集中的所有元素都被删除了。 在第二个样例中，元素 $5$、$1$、$4$、$2$ 被依次删除。 在第三个样例中，$6$ 不是唯一的答案。 由 ChatGPT 4.1 翻译