← 返回题单
题单练习 树状数组
← 上一题 下一题 →

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_i0$：表示删除第 $|k_i|$ 小的数（保证 $|k_i|$ 不超过当前多重集大小）。

输出格式

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

输入输出样例

输入 #1
5 5
1 2 3 4 5
-1 -1 -1 -1 -1
输出 #1
0
输入 #2
5 4
1 2 3 4 5
-5 -1 -3 -1
输出 #2
3
输入 #3
6 2
1 1 1 2 3 4
5 6
输出 #3
6
C++ 编辑器
输入
输出