← 返回题目列表

Codeforces · 1998/E2

E2. 通过合并消除球(困难版)

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

这是问题的困难版本。唯一的区别是这个版本中的$$$x=1$$$。您必须解决这两个版本才能进行破解。

给定两个整数 $$$n$$$ 和 $$$x$$$ ($$$x=1$$$)。有 $$$n$$$ 球排成一排,从左到右编号为 $$$1$$$ 到 $$$n$$$。最初,第 $$$i$$$ 个球上写有一个值 $$$a_i$$$。

对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$i$$$,我们定义一个函数 $$$f(i)$$$ 如下:

- 假设你有一组 $$$S = \{1, 2, \ldots, i\}$$$。
- 在每个操作中,您必须从 $$$S$$$ 中选择一个整数 $$$l$$$ ($$$1 \leq l < i$$$),使得 $$$l$$$ 不是 $$$S$$$ 的最大元素。假设$$$r$$$是$$$S$$$中大于$$$l$$$的最小元素。 如果 $$$a_l > a_r$$$,则设置 $$$a_l = a_l + a_r$$$ 并从 $$$S$$$ 中删除 $$$r$$$。 如果 $$$a_l < a_r$$$,则设置 $$$a_r = a_l + a_r$$$ 并从 $$$S$$$ 中删除 $$$l$$$。 如果 $$$a_l = a_r$$$,您可以选择整数 $$$l$$$ 或 $$$r$$$ 从 $$$S$$$ 中删除: 如果您选择从 $$$S$$$ 中删除 $$$l$$$,则设置 $$$a_r = a_l + a_r$$$ 并从 $$$S$$$ 中删除 $$$l$$$。 如果您选择从 $$$S$$$ 中删除 $$$r$$$,则设置 $$$a_l = a_l + a_r$$$ 并从 $$$S$$$ 中删除 $$$r$$$。
- $$$f(i)$$$ 表示整数 $$$j$$$ ($$$1 \le j \le i$$$) 的个数,这样在执行上述操作恰好 $$$i - 1$$$ 次后可以得到 $$$S = \{j\}$$$。

对于从 $$$x$$$ 到 $$$n$$$ 的每个整数 $$$i$$$,您需要找到 $$$f(i)$$$。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5; x = 1$$$) — 球的数量以及需要找到 $$$f(i)$$$ 的最小索引 $$$i$$$。

每个测试用例的第二行包含 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - 每个球上写的初始数字。

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

输出

对于每个测试用例,在新行上输出 $$$n-x+1$$$ 空格分隔的整数,其中第 $$$j$$$ 个整数应表示 $$$f(x+j-1)$$$。

示例

输入 #1

3
5 1
1 2 3 2 1
7 1
4 5 1 2 1 4 5
11 1
1 2 3 1 1 9 3 2 4 1 3

输出 #1

1 1 2 2 3
1 1 1 1 1 3 4
1 1 2 2 2 1 1 1 3 3 4

注意

在第一个测试用例中,以下是从 $$$1$$$ 到 $$$n$$$ 的每个 $$$f(i)$$$ 的 $$$j$$$ 的可能值。

- 对于 $$$f(1)$$$,$$$j$$$ 唯一可能的值为 $$$1$$$。
- 对于 $$$f(2)$$$,$$$j$$$ 唯一可能的值为 $$$2$$$。
- 对于 $$$f(3)$$$,$$$j$$$ 的可能值为 $$$2$$$ 和 $$$3$$$。
- 对于 $$$f(4)$$$,$$$j$$$ 的可能值为 $$$2$$$ 和 $$$3$$$。
- 对于 $$$f(5)$$$,$$$j$$$ 的可能值为 $$$2$$$、$$$3$$$ 和 $$$4$$$。