AT_abc371_g [ABC371G] Lexicographically Smallest Permutation

题目描述

给定 $(1,2,\ldots,N)$ 的一个排列 $P=(P_1,P_2,\ldots,P_N)$ 和 $A=(A_1,A_2,\ldots,A_N)$。

你可以进行任意次（包括 $0$ 次）如下操作：

• 对于 $i=1,2,\ldots,N$，同时将 $A_i$ 替换为 $A_{P_i}$。

请输出所有可能得到的 $A$ 中，字典序最小的一个。

字典序的定义如下：对于长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N)$，若存在某个整数 $i\ (1\leq i\leq N)$，使得 $A_i<B_i$，并且对于所有 $1\leq j<i$ 都有 $A_j=B_j$，则称 $A$ 的字典序小于 $B$。

输入格式

输入以如下格式从标准输入给出。

$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出所有可能得到的 $A$ 中，字典序最小的一个。输出格式为 $(A_1,A_2,\ldots,A_N)$，用空格分隔，输出一行。

输入输出样例 #1

输入 #1

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

输出 #1

1 4 2 5 3 6

输入输出样例 #2

输入 #2

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

输出 #2

1 2 3 4 5 6 7 8

输入输出样例 #3

输入 #3

26
24 14 4 20 15 19 16 11 23 22 12 18 21 3 6 8 26 2 25 7 13 1 5 9 17 10
15 3 10 1 13 19 22 24 20 4 14 23 7 26 25 18 11 6 9 12 2 21 5 16 8 17

输出 #3

4 1 22 18 20 13 14 6 15 11 3 26 2 12 5 23 9 10 25 24 7 17 16 21 19 8

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq P_i\leq N\ (1\leq i\leq N)$
• $P_i\neq P_j\ (1\leq i<j\leq N)$
• $1\leq A_i\leq N\ (1\leq i\leq N)$
• $A_i\neq A_j\ (1\leq i<j\leq N)$
• 输入均为整数

样例解释 1

初始时，$A=(4,3,1,6,2,5)$。多次操作后，序列变化如下：

• 变为 $A=(1,4,2,5,3,6)$。
• 变为 $A=(2,1,3,6,4,5)$。
• 变为 $A=(3,2,4,5,1,6)$。
• 变为 $A=(4,3,1,6,2,5)$。

之后每进行 $4$ 次操作，$A$ 会回到初始状态。因此，在这些序列中，字典序最小的是 1 4 2 5 3 6，请输出它。

样例解释 2

你也可以选择一次操作都不进行。

由 ChatGPT 4.1 翻译