← 返回题目列表

Codeforces · 2185/H

H. 战牛 2

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

Farmer John 希望举办另一场有 $$$n$$$ 头牛的锦标赛,其中第 $$$i$$$ 头牛的技能水平为 $$$a_i$$$。重复以下过程,直到队列中只有一头牛为止。

  • 队伍中的第一头牛与队伍中的第二头牛战斗,技能等级较高的牛获胜。如果平局,则第一头牛获胜。
  • 获胜奶牛的技能等级设置为 $$$x + y$$$,其中 $$$x$$$ 是获胜奶牛的技能等级,$$$y$$$ 是失败奶牛的技能等级。
  • 失败的牛离开队伍。

然而,为了保持真正的 USACOW 比赛的准确性,一头牛可以作弊多达 $$$k$$$ 次。这意味着即使输掉了比赛,Farmer John 也会将其视为失败的奶牛赢得了比赛,这意味着失败的奶牛的技能等级将被设置为 $$$x + y$$$,其中 $$$x$$$ 是获胜奶牛的技能等级,$$$y$$$ 是失败奶牛的技能等级,获胜的奶牛将离开队伍。

位置 $$$x$$$ 对于奶牛 $$$i$$$ 有好处,如果奶牛 $$$i$$$ 可以从其原始位置移除并插入到索引 $$$x$$$ 处 不改变其他牛的顺序 并且在比赛结束后成为队伍中唯一剩下的牛,假设没有其他牛作弊。

对于队列中的每头牛,计算该牛的好位置数。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \leq k \lt n$$$) — 奶牛的数量和奶牛可以使用的作弊数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 奶牛的技能水平。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数表示奶牛 $$$i$$$ 的好位置数。

示例

输入
复制

7
2 0
2 1
2 0
1 1
3 1
1 1 3
3 0
2 1 1
3 1
1 3 1
4 1
1 2 1 3
7 2
1 3 3 17 39 3 12

输出
复制

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

注意

对于第一个测试用例,牛 $$$2$$$ 无论其位置如何都会失败,而牛 $$$1$$$ 无论其位置在何处都会获胜。

对于第二个测试用例,两头牛都可以在位置 $$$1$$$ 获胜,但无法在位置 $$$2$$$ 获胜,这意味着它们各自都有 $$$1$$$ 好的位置。

对于第三个测试用例,让我们看一下奶牛 $$$1$$$。

  • 如果牛 $$$1$$$ 处于位置 $$$1$$$,那么它将赢得第一场比赛,使其技能等级等于 $$$2$$$,并且可以作弊赢得第二场比赛。
  • 如果牛 $$$1$$$ 位于 $$$2$$$ 位置,那么它必须作弊才能赢得第一场比赛,但随后会输掉第二场比赛。
  • 如果牛 $$$1$$$ 处于位置 $$$3$$$,那么它必须作弊才能赢得第一场比赛,并且不会再有比赛。