A16481 · 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$ 头奶牛的好位置数量。

输入 #1

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

输出 #1

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