ABC-470-D - Inverse and Swap

题目大意

D - Inverse and Swap

时间限制：2 秒 / 内存限制：1024 MiB

分值：$400$ 分

给定一个 $(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$ 的值。

输入从标准输入给出，格式如下：

N Q
P_1 P_2 ⋯ P_N
query_1
⋮
query_Q

其中 $\mathrm{query}_q$ 表示第 $q$ 个询问，以下面两种格式之一给出：

1 x y

2

将处理完所有询问后 $P_1, \dots, P_N$ 的值以空格分隔，输出在一行中。

• $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$

• 输入中的所有值均为整数

输入

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)$

输入

7 4
3 7 5 6 4 2 1
2
2
2
2

输出

3 7 5 6 4 2 1

说明

本样例中的 $4$ 个询问均为类型 $2$，处理完成后 $P$ 与初始时相同。

输入

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都可以看成是一个只有一条出边的有向图邻接表啊，那么实际上，我们存储的就是这个无向图啊。因为无向图就是一条边有两个方向的有向图嘛。

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

AI 代码

#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;
}

源代码

心路历程（WA，TLE，MLE……）