← 返回题目列表

Codeforces · 1746/C

C. 排列运算

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

给你一个大小为 $$$n$$$ 的排列 $$$a$$$,你应该对其执行 $$$n$$$ 操作。在第 $$$i$$$ 操作中,您可以选择 $$$a$$$ 的非空后缀,并将其所有元素增加 $$$i$$$。我们如何执行操作来最小化最终数组中的反转次数?

请注意,您可以对同一后缀执行任意次数的操作。

大小 $$$n$$$ 的排列是大小为 $$$n$$$ 的数组,使得从 $$$1$$$ 到 $$$n$$$ 的每个整数在此数组中恰好出现一次。后缀是数组的几个连续元素,包括数组的最后一个元素。数组 $$$a$$$ 中的反转是一对索引 $$$(i, j)$$$,使得 $$$i > j$$$ 且 $$$a_{i} < a_{j}$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的大小。

第二行包含 $$$n$$$ 不同的整数 $$$a_{1}, a_{2}, \dots, a_{n}$$$ ($$$1 \le a_i \le n$$$),初始排列 $$$a$$$。

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

输出

对于每个测试用例,打印 $$$n$$$ 整数 $$$x_{1}, x_{2}, \ldots, x_{n}$$$ ($$$1 \le x_{i} \le n$$$ 对于每个 $$$1 \le i \le n$$$) 指示第 $$$i$$$ 操作必须应用于从索引开始的后缀$$$x_{i}$$$。如果有多个答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

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

注意

在第一个测试用例中,最佳解决方案之一是在每个操作上增加整个数组(即选择从索引 $$$1$$$ 开始的后缀)。最终数组 $$$[11, 12, 13, 14]$$$ 包含 $$$0$$$ 反转。

在第二个测试用例中, $$$a$$$ 将等于 $$$[2, 4, 3, 5, 6]$$$, $$$[2, 4, 3, 7, 8]$$$, $$$[2, 4, 6, 10, 11]$$$, $$$[2, 8, 10, 14, 15]$$$ 和 $$$[7, 13, 15, 19, 20]$$$ 分别在第一次、第二次、第三次、第四次和第五次操作之后。所以最终的数组 $$$a$$$ 具有零个反转。