AT_abc371_g.[ABC371G] Lexicographically Smallest Permutation
省选/NOI-
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
给定 $ (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
6 3 1 5 6 2 4 4 3 1 6 2 5
输出#1
1 4 2 5 3 6
输入#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
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 翻译
输入解题思路，AI测评打分。不知道怎么写?