问题2234--Black Box（P1801、UVA501）

2234: Black Box（P1801、UVA501）

时间限制: 1 Sec  内存限制: 128 MB
提交: 13  解决: 10
[提交] [状态] [讨论版] [命题人:]

题目描述

黑匣子（Black Box）代表一个原始的数据库。它可以用来储存整数数组，并且它拥有一个特殊变量 i，在最开始，黑匣子是空的，并且i=0。现在对黑匣子进行一系列的操作处理，操作包括以下两种：
（1）ADD(x)：表示将 x 加入到黑匣子中。
（2）GET：使 i 增加1，输出黑匣子中第 i 小的数值（即将所有数按升序排序后的第 i 个数）。
我们来演示一下一个有11个命令的命令串（如下表示）

序号

操作

i

数据库

输出

1

ADD(3)

0

3

/

2

GET

1

3

3

3

ADD(1)

1

1,3

/

4

GET

2

1,3

3

5

ADD(-4)

2

-4,1,3

/

6

ADD(2)

2

-4,1,2,3

/

7

ADD(8)

2

-4,1,2,3,8

/

8

ADD(-1000)

2

-1000,-4,1,2,3,8

/

9

GET

3

-1000,-4,1,2,3,8

1

10

GET

4

-1000,-4,1,2,3,8

2

11

ADD(2)

4

-1000,-4,1,2,2,3,8

/

现在要求找出对于给定的命令串的最好的处理方法。ADD命令共有m个，GET命令共有n个。现在用两个整数数组来表示命令串。
（1）a1,a2,···,am:一串将要被放进黑匣子的元素。例如，上面的例子中a=[3,1,-4,2,8,-1000,2]。
（2）u1,u2,···,un:表示第ui个元素被放进了黑匣子里后就出现一个GET命令。例如，上面的例子中u=[1,2,6,6]。输入数据不用判错。

输入

输入包括三行。
第一行包含两个整数M和N，表示A序列和u序列的长度。
第二行包含M个整数，表示A序列的每一个元素。
第三行包含N个整数，表示u序列的每一个元素。
同行每个数之间用空格隔开。

输出

输出操作过程中所有GET操作输出的数值。每个数值占一行。

样例输入 Copy 

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

样例输出 Copy 

3
3
1
2

提示

|A(i)|≤2×109,1≤N，M≤2×105。
保证U序列单调不降。

来源/分类

堆 优先队列 
[提交] [状态]