ABC-470-D - Inverse and Swap · znzryb
## 题目大意
### D - Inverse and Swap
时间限制:2 秒 / 内存限制:1024 MiB
分值:$400$ 分
<!-- Notion block type: heading_4 -->
给定一个 $(1, \dots, N)$ 的排列 $P = (P_1, \dots, P_N)$。
请依次处理 $Q$ 个询问,询问有以下两种:
- `1 x y`:交换 $P_x$ 与 $P_y$ 的值。
- `2`:构造满足以下条件的 $(1, \dots, N)$ 的排列 $P' = (P'_1, \dots, P'_N)$,并将 $P_1, \dots, P_N$ 的值分别替换为 $P'_1, \dots, P'_N$。(可以证明满足条件的 $P'$ 唯一存在。)
- 对每个满足 $1 \leq i \leq N$ 的整数 $i$,都有 $P_{P'_i} = i$。
请输出处理完所有询问后 $P_1, \dots, P_N$ 的值。
<!-- Notion block type: heading_4 -->
输入从标准输入给出,格式如下:
```
N Q
P_1 P_2 ⋯ P_N
query_1
⋮
query_Q
```
其中 $\mathrm{query}_q$ 表示第 $q$ 个询问,以下面两种格式之一给出:
```
1 x y
```
```
2
```
<!-- Notion block type: heading_4 -->
将处理完所有询问后 $P_1, \dots, P_N$ 的值以空格分隔,输出在一行中。
<!-- Notion block type: heading_4 -->
- $2 \leq N \leq 5 \times 10^5$
- $1 \leq Q \leq 5 \times 10^5$
- $(P_1, \dots, P_N)$ 是 $(1, \dots, N)$ 的排列
- 对于类型 $1$ 的询问,$1 \leq x < y \leq N$
- 输入中的所有值均为整数
<!-- Notion block type: heading_4 -->
**输入**
```
5 5
2 1 3 5 4
1 2 4
2
1 2 3
1 3 4
2
```
**输出**
```
4 5 2 1 3
```
**说明**
每个询问处理完成时,$P_1, \dots, P_N$ 的值如下:
- 处理完第 $1$ 个询问时,$P = (2,5,3,1,4)$
- 处理完第 $2$ 个询问时,$P = (4,1,3,5,2)$
- 处理完第 $3$ 个询问时,$P = (4,3,1,5,2)$
- 处理完第 $4$ 个询问时,$P = (4,3,5,1,2)$
- 处理完第 $5$ 个询问时,$P = (4,5,2,1,3)$
<!-- Notion block type: heading_4 -->
**输入**
```
7 4
3 7 5 6 4 2 1
2
2
2
2
```
**输出**
```
3 7 5 6 4 2 1
```
**说明**
本样例中的 $4$ 个询问均为类型 $2$,处理完成后 $P$ 与初始时相同。
<!-- Notion block type: heading_4 -->
**输入**
```
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 10 2 8 6 7 1 5 9 4
```
**说明**
本样例包含两种询问混合出现的情况,请按照询问给出的顺序依次处理。
## 思路讲解

那么实际上,**排列就是位置和值的对应关系啊**,**至于箭头的方向和哪边是位置,哪边是值**,这个其实不是特别重要啊,用一个变量 f 维护一下即可啊。
那么这个叫什么**交换操作就只是需要修改一下这个对应关系**即可啊,这个就非常简单,你可以理解为我们就是一个**无向图**啊,然后**最后再进行定向即可**啊。
当然,还是要注意一下值和位置当前的对应关系啊。
存储的时候,S 和 T都可以看成是一个只有一条出边的有向图邻接表啊,那么实际上,我们存储的就是这个无向图啊。因为无向图就是一条边有两个方向的有向图嘛。
```cpp
int mp[2][500005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> mp[0][i]; // 位置 i —— 值 mp[0][i]
mp[1][mp[0][i]] = i; // 同一条边,从值那一侧再记一遍
}
int f = 0; // 定向标记
while (q--) {
int op;
cin >> op;
if (op == 2) {
f ^= 1; // 换个方向读,O(1)
continue;
}
int x, y;
cin >> x >> y;
int *S = mp[f]; // 当前的"位置侧"
int *T = mp[f ^ 1]; // 对侧
int u = S[x], v = S[y]; // 原来 x—u、y—v 两条边
// 拆掉 x—u、y—v,重连成 x—v、y—u
// 用 tie + make_tuple 一次性赋值:右边先整体求值,
// 天然避开"先改哪个、后改哪个"的顺序陷阱
tie(S[x], S[y], T[u], T[v]) = make_tuple(v, u, y, x);
}
// 最后按 f 定向,输出对应的那一侧
const int *R = mp[f];
for (int i = 1; i <= n; i++)
cout << R[i] << " \n"[i == n];
return 0;
}
```
## AC代码
[https://atcoder.jp/contests/abc470/submissions/78275932](https://atcoder.jp/contests/abc470/submissions/78275932)
::: AI 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
/* ------------------------------------------------------------------
模型:排列 = 位置集 与 值集 之间的完美匹配(无向)
mp[0][i] : 从"位置侧"看,位置 i 连到哪个值
mp[1][v] : 从"值侧"看,值 v 连到哪个位置
两者存的是同一个匹配,只是从两侧各记一遍邻接。
f = 当前把哪一侧当作"位置"来读(即定向)
f = 0 -> 真正的 P 就是 mp[0]
f = 1 -> 真正的 P 是 mp[1](相当于整体取了逆)
操作 2:只改定向,f ^= 1,不动任何数据
操作 1:在当前"位置侧" S 上把 x,y 两条边的另一端对调,
同时在对侧 T 上把这两个端点的记录改回来,共 4 个格子
------------------------------------------------------------------ */
int mp[2][500005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> mp[0][i]; // 位置 i —— 值 mp[0][i]
mp[1][mp[0][i]] = i; // 同一条边,从值那一侧再记一遍
}
int f = 0; // 定向标记
while (q--) {
int op;
cin >> op;
if (op == 2) {
f ^= 1; // 换个方向读,O(1)
continue;
}
int x, y;
cin >> x >> y;
int *S = mp[f]; // 当前的"位置侧"
int *T = mp[f ^ 1]; // 对侧
int u = S[x], v = S[y]; // 原来 x—u、y—v 两条边
// 拆掉 x—u、y—v,重连成 x—v、y—u
// 用 tie + make_tuple 一次性赋值:右边先整体求值,
// 天然避开"先改哪个、后改哪个"的顺序陷阱
tie(S[x], S[y], T[u], T[v]) = make_tuple(v, u, y, x);
}
// 最后按 f 定向,输出对应的那一侧
const int *R = mp[f];
for (int i = 1; i <= n; i++)
cout << R[i] << " \n"[i == n];
return 0;
}
```
:::
::: 源代码
```cpp
```
:::
## 心路历程(WA,TLE,MLE……)