#754. 【提高】黑盒子

【提高】黑盒子

题目描述

Black Box 是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量 ii。最开始的时候 Black Box 是空的.而 i=0i=0。这个 Black Box 要处理一串命令。

命令只有两种:

  • ADD(x):把 xx 元素放进 Black Box;

  • GETii11,然后输出 Black Box 中第 ii 小的数。

记住:第 ii 小的数,就是 Black Box 里的数的按从小到大的顺序排序后的第 ii 个元素。

我们来演示一下一个有11个命令的命令串。(如下表所示)

序号 操作 ii 数据库 输出
1 ADD(3) 00 33 /
2 GET 11 33
3 ADD(1) 1,31,3 /
4 GET 22 33
5 ADD(-4) 4,1,3-4,1,3 /
6 ADD(2) 4,1,2,3-4,1,2,3
7 ADD(8) 4,1,2,3,8-4,1,2,3,8
8 ADD(-1000) 1000,4,1,2,3,8-1000,-4,1,2,3,8
9 GET 33 11
10 44 22
11 ADD(2) 1000,4,1,2,2,3,8-1000,-4,1,2,2,3,8 /

现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 mm 个,GET 命令共有 nn 个。现在用两个整数数组来表示命令串:

  1. a1,a2,,ama_1,a_2,\cdots,a_m:一串将要被放进 Black Box 的元素。例如上面的例子中 a=[3,1,4,2,8,1000,2]a=[3,1,-4,2,8,-1000,2]

  2. u1,u2,,unu_1,u_2,\cdots,u_n:表示第 uiu_i 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 u=[1,2,6,6]u=[1,2,6,6] 。输入数据不用判错。

输入格式

第一行两个整数 mmnn,表示元素的个数和 GET 命令的个数。

第二行共 mm 个整数,从左至右第 ii 个整数为 aia_i,用空格隔开。

第三行共 nn 个整数,从左至右第 ii 个整数为 uiu_i,用空格隔开。

输出格式

输出 Black Box 根据命令串所得出的输出串,一个数字一行。

样例

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

数据规模与约定

  • 对于 30%30\% 的数据,1n,m1041 \leq n,m \leq 10^{4}
  • 对于 50%50\% 的数据,1n,m1051 \leq n,m \leq 10^{5}
  • 对于 100%100\% 的数据,$1 \leq n,m \leq 2 \times 10^{5},|a_i| \leq 2 \times 10^{9}$,保证 uu 序列单调不降。

来源

  • POJ1442
  • ICPC NEERC 1996
  • NOI导刊2010提高(06)