分数: 333 分
问题陈述
高桥是一家工厂的质量控制经理。工厂有定期检查出厂产品质量的制度,对不符合标准的产品进行处理。
工厂目前有 N 产品,每个编号来自 1 to N。产品质量评分 i is A_i.
高桥表演 Q 质量检验有序。在 j第次检查 (1 \leq j \leq Q),阈值 设置 T_j ,并且 属于当时尚未处置的产品,所有质量得分为 严格小于 T_j 已被处置。产品一旦被处置,就不再接受后续检查。注意阈值 T_j 是针对每次检查独立确定的,因此它可能小于之前的阈值。在此情况下,如果相关产品在之前的检查中已经被处置,则不再处置新产品。
每次检查后,立即记录该次检查中新处置的产品数量。对于所有人 Q 质量检验,确定每次检验新处置的产品数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq T_j \leq 10^9 (1 \leq j \leq Q)
- 所有输入值均为整数。
输入
N Q A_1 A_2 \ldots A_N T_1 T_2 \vdots T_Q
- 第一行包含一个整数 N 代表产品数量和一个整数 Q 代表质检次数,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个产品的质量分数,以空格分隔。
- 在下面 Q 行, j第行 (1 \leq j \leq Q) 包含一个整数 T_j 代表阈值 j-次检查。
输出
输出 Q 行。的 j第行 (1 \leq j \leq Q) 应包含新处置的产品数量 j-次检查。
示例输入 1
5 3 3 1 4 1 5 2 4 3
示例输出 1
2 1 0
示例输入 2
8 5 10 5 3 8 7 2 6 1 4 3 7 7 9
示例输出 2
3 0 2 0 2
示例输入 3
15 6 15 3 9 7 12 1 20 5 11 2 8 18 4 6 14 5 10 8 15 15 1000000000
示例输出 3
4 5 0 3 0 3