A7710. Inverse and Swap
编程题
普及/提高-
知识点
题目描述
给定一个 $1$ 到 $N$ 的排列
$$ P=(P_1,P_2,\ldots,P_N). $$
接下来依次处理 $Q$ 次操作。
操作共有以下两种：
-
-
$$ P'=(P'_1,P'_2,\ldots,P'_N), $$
满足对于所有 $1\le i\le N$：
$$ P'_{P_i}=i. $$
然后使用 $P'$ 替换当前的 $P$。
可以证明，满足上述条件的排列 $P'$ 唯一存在。
处理完全部操作之后，输出 $P_1,P_2,\ldots,P_N$。
$$ P=(P_1,P_2,\ldots,P_N). $$
接下来依次处理 $Q$ 次操作。
操作共有以下两种：
-
1 x y：交换 $P_x$ 和 $P_y$ 的值。-
2：构造一个 $1$ 到 $N$ 的排列$$ P'=(P'_1,P'_2,\ldots,P'_N), $$
满足对于所有 $1\le i\le N$：
$$ P'_{P_i}=i. $$
然后使用 $P'$ 替换当前的 $P$。
可以证明，满足上述条件的排列 $P'$ 唯一存在。
处理完全部操作之后，输出 $P_1,P_2,\ldots,P_N$。
输入格式
输入格式如下：
```text
N Q
P1 P2 ⋯ PN
query1
⋮
queryQ
```
其中，第 $q$ 次操作
```text
1 x y
```
或者
```text
2
```
```text
N Q
P1 P2 ⋯ PN
query1
⋮
queryQ
```
其中，第 $q$ 次操作
queryq 为以下两种格式之一：```text
1 x y
```
或者
```text
2
```
输出格式
在一行中输出最终的
$$ P_1,P_2,\ldots,P_N, $$
相邻两个数之间用空格分隔。
$$ P_1,P_2,\ldots,P_N, $$
相邻两个数之间用空格分隔。
输入输出样例
输入 #1
5 5 2 1 3 5 4 1 2 4 2 1 2 3 1 3 4 2
输出 #1
4 5 2 1 3
输入 #2
7 4 3 7 5 6 4 2 1 2 2 2 2
输出 #2
3 7 5 6 4 2 1
输入 #3
10 8 7 3 2 4 8 5 10 9 1 6 2 1 4 10 1 6 9 2 1 9 10 1 3 10 2 1 4 6
输出 #3
3 10 2 8 6 7 1 5 9 4
说明/提示
### 样例一解释
每次操作执行结束后，$P$ 分别为：
- 第一次操作后：$P=(2,5,3,1,4)$。
- 第二次操作后：$P=(4,1,3,5,2)$。
- 第三次操作后：$P=(4,3,1,5,2)$。
- 第四次操作后：$P=(4,3,5,1,2)$。
- 第五次操作后：$P=(4,5,2,1,3)$。
### 数据范围
- $2\le N\le5\times10^5$
- $1\le Q\le5\times10^5$
- $(P_1,P_2,\ldots,P_N)$ 是 $1$ 到 $N$ 的一个排列。
- 对于类型 $1$ 的操作，满足 $1\le x<y\le N$。
- 所有输入值均为整数。
每次操作执行结束后，$P$ 分别为：
- 第一次操作后：$P=(2,5,3,1,4)$。
- 第二次操作后：$P=(4,1,3,5,2)$。
- 第三次操作后：$P=(4,3,1,5,2)$。
- 第四次操作后：$P=(4,3,5,1,2)$。
- 第五次操作后：$P=(4,5,2,1,3)$。
### 数据范围
- $2\le N\le5\times10^5$
- $1\le Q\le5\times10^5$
- $(P_1,P_2,\ldots,P_N)$ 是 $1$ 到 $N$ 的一个排列。
- 对于类型 $1$ 的操作，满足 $1\le x<y\le N$。
- 所有输入值均为整数。