#STL012. 区间定位仪

区间定位仪

区间定位仪

给你一列顺序任意的整数,以及若干查询值。对每个查询值 x,请分别统计原序列中有多少个元素小于 x、等于 x、大于 x。

重复元素要按出现次数计算。例如序列中有三个 4,查询 4 时,“等于”的数量就包括这三个元素。查询不会修改原序列。原序列允许为空,此时每次查询的三个数量都为 0。

输入格式

第一行两个整数 n、q。接着给出 n 个整数,表示原序列。通常写在第二行;n=0 时该行可以为空。之后给出 q 个查询值,每行一个整数。

输出格式

对每个查询按输入顺序输出一行三个整数,依次为小于 x、等于 x、大于 x 的元素数量,以空格分隔。每一行三个数量的和应为 n。

数据范围

  • 0 ≤ n ≤ 200000。
  • 1 ≤ q ≤ 200000。
  • 原序列元素及查询值均在 [−10⁹, 10⁹] 内。
  • 原序列无排序保证,允许重复。

样例 1

输入:

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

输出:

2 3 1
0 0 6
6 0 0
0 1 5
2 0 4

解释:查询 4 时,−2 和 1 小于 4,三个 4 等于 4,7 大于 4,因此输出 2 3 1。查询 −3 和 8 分别位于所有元素的左侧和右侧,等于数量均为 0。

样例 2

输入:

0 3

0
-1
1

输出:

0 0 0
0 0 0
0 0 0

解释:n=0,原序列为空。三个查询值无论大小如何,三种元素数量都为 0。