← 返回题目列表

Codeforces · 2048/D

D. 凯文和比赛回忆

中文机器翻译题面 查看原题

凯文曾经进入过里约的回忆,里约的回忆里曾经举办过一系列的比赛。凯文记得当时的所有参赛者和所有比赛问题,但他忘记了具体的轮次、问题的分布以及确切的排名。

总共有 $$$ m $$$ 问题,其中第 $$$ i $$$ 问题的难度为 $$$ b_i $$$。让每场比赛由 $$$ k $$$ 问题组成,总共产生 $$$ \lfloor \frac{m}{k} \rfloor $$$ 比赛。这意味着您可以按照您想要的任意组合为比赛精确选择 $$$ \lfloor \frac{m}{k} \rfloor \cdot k $$$ 问题,每个问题最多选择一次,其余 $$$m\bmod k$$$ 问题将不使用。例如,如果 $$$m = 17$$$ 且 $$$k = 3$$$,则您应该创建恰好 $$$5$$$ 竞赛,每个竞赛包含 $$$3$$$ 问题,并且恰好 $$$2$$$ 问题将被闲置。

比赛共有 $$$ n $$$ 名参与者,Kevin 是第 $$$1$$$ 名参与者。第 $$$ i $$$ 参与者的评级为 $$$ a_i $$$。在比赛期间,每个参与者都以不超过其评分的难度解决所有问题,这意味着第 $$$ i $$$ 个参与者解决了第 $$$ j $$$ 个问题当且仅当 $$$ a_i \geq b_j $$$。在每次比赛中,凯文的排名是比他解决更多问题的参与者人数加一。

对于每个 $$$ k = 1, 2, \ldots, m $$$,Kevin 想知道他在所有 $$$ \lfloor \frac{m}{k} \rfloor $$$ 比赛中的排名的最小总和。换句话说,对于 $$$k$$$ 的某个值,在为每次比赛选择问题后,您可以计算 Kevin 在每次比赛中的排名,并将所有 $$$ \lfloor \frac{m}{k} \rfloor $$$ 比赛的排名相加。您的目标是最小化该值。

请注意,不同 $$$k$$$ 值的竞赛是独立的。这意味着对于不同的 $$$k$$$ 值,您可以独立选择问题在竞赛中的分布。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$ t $$$ ($$$ 1 \le t \le 5\cdot 10^4 $$$)。

每个测试用例的第一行包含两个整数 $$$ n $$$ 和 $$$ m $$$ ($$$ 1 \le n, m \leq 3\cdot 10^5 $$$) - 参与者数量和问题数量。

每个测试用例的第二行包含 $$$ n $$$ 整数 $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 0 \le a_i \le 10^9 $$$) - 每个参与者的评分。

每个测试用例的第三行包含 $$$ m $$$ 整数 $$$ b_1, b_2, \ldots, b_m $$$ ($$$ 0 \le b_i \le 10^9 $$$) - 每个问题的难度。

保证所有测试用例的 $$$ n $$$ 之和以及 $$$ m $$$ 之和不超过 $$$ 3 \cdot 10^5 $$$。

输出

对于每个测试用例,输出 $$$m$$$ 整数 - 每个 $$$ k = 1, 2, \ldots, m$$$ 的 Kevin 排名的最小总和。

示例

输入 #1

4
4 4
4 3 7 5
2 5 4 6
5 5
5 0 4 8 6
1 3 9 2 7
6 7
1 1 4 5 1 4
1 9 1 9 8 1 0
7 6
1 9 1 9 8 1 0
1 1 4 5 1 4

输出 #1

7 4 2 3
6 2 1 1 2
7 3 2 1 1 1 1
15 9 5 4 4 4

注意

对于第一个测试用例:

当 $$$k=1$$$ 时,由于每次竞赛仅包含一个问题,因此分布实际上是唯一的。例如,在仅包括第三个问题(难度为$$$4$$$)的竞赛中,除了$$$2$$$-nd之外的所有参与者都可以解决它。由于严格意义上没有人比 Kevin 解决更多问题,因此他在本次比赛中的排名为 $$$1$$$。同样,在所有 $$$4$$$ 比赛中,Kevin 的排名为 $$$1,3,1,2$$$,总和为 $$$7$$$。

当$$$k=2$$$时,一种最佳方法是选择$$$1$$$-st和$$$3$$$-rd问题进行竞赛,而$$$2$$$-nd和$$$4$$$-th作为另一个竞赛。在上一场比赛中,$$$4$$$参与者分别解决了$$$2,1,2,2$$$问题,因此Kevin的排名为$$$1$$$;在后一项中,他们分别解决了$$$0,0,2,1$$$,由于有$$$2$$$参与者($$$3$$$-rd和$$$4$$$-th)比Kevin解决了更多问题,他的排名是$$$1+2=3$$$。因此答案是$$$1+3=4$$$。可以证明,没有办法达到更低的总和。

当$$$k=3$$$时,我们可以简单地选择$$$1$$$-st、$$$3$$$-rd和第$$$4$$$-th问题进行竞赛,Kevin的排名为$$$2$$$,这是最优的。

当$$$k=4$$$时,由于只有一场比赛,分布也是唯一的,Kevin的排名是$$$3$$$。