← 返回题目
题库练习 Inverse and Swap
← 上一题 下一题 →

A7710 | Inverse and Swap

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

给定一个 $1$ 到 $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$ 次操作 queryq 为以下两种格式之一：

```text
1 x y
```

或者

```text
2
```

输出格式

在一行中输出最终的

$$ 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
C++ 编辑器
输入
输出