← 返回题目

题库练习多重集

← 上一题下一题 →

A6898 | $多重集$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个包含 $n$ 个整数的**多重集**。你需要处理两种类型的操作： - 向多重集中添加整数 $k$； - 查询并删除多重集中第 $k$ 小的数。 多重集中的第 $k$ 小数：把所有元素从小到大排序后，第 $k$ 个元素。若某个数出现多次，删除时只删掉其中一个。 所有操作完成后： - 如果多重集为空，输出 $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\cdots\le a_n\le n$）。 第三行 $q$ 个整数 $k_1,k_2,\ldots,k_q$： - 若 $1\le k_i\le n$：表示插入 $k_i$； - 若 $k_i<0$：表示删除第 $|k_i|$ 小的数（保证 $|k_i|$ 不超过当前多重集大小）。

输出格式

若最终多重集为空输出 $0$，否则输出任意一个元素。

输入输出样例

输入 #1

5 5
1 2 3 4 5
-1 -1 -1 -1 -1

输出 #1

输入 #2

5 4
1 2 3 4 5
-5 -1 -3 -1

输出 #2

输入 #3

6 2
1 1 1 2 3 4
5 6

输出 #3

C++ 编辑器

输入

输出