CF2185H BattleCows 2

农夫 John 想举办另一场 $n$ 头奶牛的锦标赛，其中第 $i$ 头奶牛的实力为 $a_i$。如下过程会不断重复，直到队列中只剩下一头奶牛。 - 队列中的第一头奶牛与第二头奶牛对决，实力较高者胜出。如果实力相同，则第一头奶牛胜出。 - 获胜奶牛的实力会变为 $x + y$，其中 $x$ 为胜者原有的实力，$y$ 为失者的实力。 - 输掉的奶牛将离开队列。 然而，为了更贴近真实的 USACOW 比赛，每头奶牛最多可以作弊 $k$ 次。这意味着即使在比赛中输了，农夫 John 也会认为失败的奶牛赢得了比赛，此时输的奶牛的实力会变为 $x + y$（$x$ 是赢家的实力，$y$ 是输家的实力），而原本的赢家将离开队列。 如果将奶牛 $i$ 从原来的位置移除，并插入到位置 $x$ （保持其他奶牛的顺序不变），且在没有其它奶牛作弊的情况下，最后只有她能留在队列中，则称位置 $x$ 对于奶牛 $i$ 来说是一个好位置。 对于每头奶牛，计算其拥有多少个好位置。

输入的第一行为一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。 每个测试用例的第一行为两个整数 $n$ 和 $k$（$2 \le n \le 2 \times 10^5$，$0 \leq k < n$）——表示奶牛数量和每头奶牛可以作弊的次数。 第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——表示每头奶牛的实力。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

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

对于第一个测试用例，无论奶牛 2 站在哪个位置，她都会输，而奶牛 1 无论站在哪个位置都会赢。 对于第二个测试用例，奶牛 1 和奶牛 2 都只在位置 1 时能获胜，在位置 2 都无法获胜，所以每头奶牛都有 1 个好位置。 对于第三个测试用例，考察奶牛 1： - 如果奶牛 1 在第 1 个位置，她会赢得首场比赛，实力变为 2，并可以作弊赢得第二场比赛。 - 如果奶牛 1 在第 2 个位置，她需要作弊赢得首场比赛，但之后会输掉第二场。 - 如果奶牛 1 在第 3 个位置，她需要作弊赢得首场比赛，随后比赛结束，不再有对决。 由 ChatGPT 5 翻译