#P1801. 黑匣子
黑匣子
题目描述
Black Box 是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量 。最开始的时候 Black Box 是空的.而 。这个 Black Box 要处理一串命令。
命令只有两种:
-
ADD(x)
:把 元素放进 Black Box; -
GET
: 加 ,然后输出 Black Box 中第 小的数。
记住:第 小的数,就是 Black Box 里的数的按从小到大的顺序排序后的第 个元素。
我们来演示一下一个有11个命令的命令串。(如下表所示)
序号 | 操作 | 数据库 | 输出 | |
---|---|---|---|---|
1 | ADD(3) |
/ | ||
2 | GET |
|||
3 | ADD(1) |
/ | ||
4 | GET |
|||
5 | ADD(-4) |
/ | ||
6 | ADD(2) |
|||
7 | ADD(8) |
|||
8 | ADD(-1000) |
|||
9 | GET |
|||
10 | ||||
11 | ADD(2) |
/ |
现在要求找出对于给定的命令串的最好的处理方法。ADD
命令共有 个,GET
命令共有 个。现在用两个整数数组来表示命令串:
-
:一串将要被放进 Black Box 的元素。例如上面的例子中 。
-
:表示第 个元素被放进了 Black Box 里后就出现一个
GET
命令。例如上面的例子中 。输入数据不用判错。
输入格式
第一行两个整数 和 ,表示元素的个数和 GET
命令的个数。
第二行共 个整数,从左至右第 个整数为 ,用空格隔开。
第三行共 个整数,从左至右第 个整数为 ,用空格隔开。
输出格式
输出 Black Box 根据命令串所得出的输出串,一个数字一行。
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
3
3
1
2
提示
数据规模与约定
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,$1 \leq n,m \leq 2 \times 10^{5},|a_i| \leq 2 \times 10^{9}$,保证 序列单调不降。