103716: [Atcoder]ABC371 G - Lexicographically Smallest Permutation
Description
Score : $575$ points
Problem Statement
You are given permutations $P = (P_1, P_2, \ldots, P_N)$ and $A = (A_1, A_2, \ldots, A_N)$ of $(1,2,\ldots,N)$.
You can perform the following operation any number of times, possibly zero:
- replace $A_i$ with $A_{P_i}$ simultaneously for all $i=1,2,\ldots,N$.
Print the lexicographically smallest $A$ that can be obtained.
What is lexicographical order?
For sequences of length $N$, $A = (A_1, A_2, \ldots, A_N)$ and $B = (B_1, B_2, \ldots, B_N)$, $A$ is lexicographically smaller than $B$ if and only if:
- there exists an integer $i\ (1\leq i\leq N)$ such that $A_i < B_i$, and $A_j = B_j$ for all $1\leq j < i$.
Constraints
- $1\leq N\leq2\times10^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)$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Let $(A_1, A_2, \ldots, A_N)$ be the lexicographically smallest $A$ that can be obtained. Print $A_1, A_2, \ldots, A_N$ in this order, separated by spaces, in one line.
Sample Input 1
6 3 1 5 6 2 4 4 3 1 6 2 5
Sample Output 1
1 4 2 5 3 6
Initially, $A = (4, 3, 1, 6, 2, 5)$.
Repeating the operation yields the following.
- $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)$
After this, $A$ will revert to the original state every four operations.
Therefore, print the lexicographically smallest among these, which is 1 4 2 5 3 6.
Sample Input 2
8 3 5 8 7 2 6 1 4 1 2 3 4 5 6 7 8
Sample Output 2
1 2 3 4 5 6 7 8
You may choose to perform no operations.
Sample Input 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
Sample Output 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
Output
得分：575分
问题陈述
给你两个排列 $P = (P_1, P_2, \ldots, P_N)$ 和 $A = (A_1, A_2, \ldots, A_N)$，它们都是 $(1,2,\ldots,N)$ 的排列。
你可以执行以下操作任意多次，可能为零次：
- 同时将 $A_i$ 替换为 $A_{P_i}$ 对于所有 $i=1,2,\ldots,N$。
打印可以获得的字典序最小的 $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$。
约束条件
- $1\leq N\leq2\times10^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)$
- 所有输入值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $P_1$ $P_2$ $\ldots$ $P_N$ $A_1$ $A_2$ $\ldots$ $A_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
初始时，$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)$
此后，每四次操作后 $A$ 将恢复到原始状态。
因此，打印这些中的字典序最小者，即 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
你可能