黑匣子

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 blackbox.in 输出文件 blackbox.out
【问题描述】
我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令： ADD(x)：把元素x放入黑匣子；GET：把i加1的同时，输出黑匣子内所有整数中第i小的数。牢记第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和GET命令的总数至多有30000个。定义ADD命令的个数为M个，GET命令的个数为N个。我们用下面的两个整数序列描述命令序列：
(1)A(1)，A(2)，…，A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A＝(3，1，-4，2，8，-1000，2)。
(2)u(1)，u(2)，…，u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u＝(1，2，6，6)。
你可以假定自然数序列u(1)，u(2)，…，u(N)以非降序排列，N≤M，且对于每一个p(1≤p≤N)有p≤u(p)≤M。

【输入格式】
     输入文件名为blackbox.in，其中第一行存放M和N的值，第二行存放A(1)，A(2)，…，
A(M)，第三行存放u(1)，u(2)，…，u(N)。
【输出格式】
   输出黑匣子的处理结果。
【输入输出样例】 
输入:
blackbox.in
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
输出:
blackbox.out
3
3
1
2