← 返回题目列表

AtCoder · arc167_d

D. 良好的排列

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

分数: 700 点

问题陈述

在这个问题中,当我们说“排列”时,它指的是 (1,2,\dots,N).

给你一个排列 P=(P_{1},P_{2},\dots,P_{N}).

排列 当以下条件成立时, Q=(Q_{1},Q_{2},\dots,Q_{N}) 被认为是一个很好的排列。

  • 对于每个整数 1\leq x\leq N,可以使 x 等于 1 通过重复替换 x\leftarrow Q_{x} 一些次。

你想要 P 通过执行以下操作得到一个好的排列 P 零次或多次。

  • 选择整数 i 和 j 这样 1\leq i\lt j \leq N,并交换 P_{i} 和 P_{j}.

让 M 是必须执行该操作才能使 P 一个很好的排列。找到通过执行该操作可以获得的按字典顺序最小的好排列 M 次 P.

对于每个输入文件,您有 T 测试用例解决。

序列的字典顺序是什么?

一个序列 非负整数的 S = (S_1,S_2,\ldots,S_{|S|}) 据说是 按字典顺序较小 比序列 T = (T_1,T_2,\ldots,T_{|T|}) 当以下1.或2.之一成立时。 在这里, |S| 和 |T| 表示的长度 S 和 T。

  1. |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
  2. 有一个整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace 满足以下两项。
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
    • S_i 小于 T_i (作为数字)。

约束

  • 1\leq T\leq 10^{5}
  • 2\leq N\leq 2\times 10^{5}
  • (P_{1},P_{2},\dots ,P_{N}) 是一个排列 (1,2,\dots ,N).
  • 对于每个输入文件,总和 N 不超过 2\times 10^{5}.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}

每个案例均按以下格式给出:

N
P_{1} P_{2} \cdots P_{N}

输出

打印 T 行。 的 i-th 行应包含作为答案的排列 \text{case}_{i},用空格分隔。


示例输入 1

5
4
2 1 4 3
5
2 1 3 4 5
2
1 2
2
2 1
9
4 3 6 2 7 1 9 8 5

示例输出 1

2 3 4 1
2 3 4 5 1
2 1
2 1
4 3 5 2 7 1 8 9 6

对于第一个测试用例:

P 不是一个好的排列。交换 P_{1} 和 P_{3} 使 P=(4,1,2,3),这是一个很好的排列,所以 M=1。 除此之外,交换 P_{2} 和 P_{4} 使 P=(2,3,4,1),这是按字典顺序可以获得的最小的好排列 M=1 操作,所以这就是答案。