#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。