题解：AT_abc470_d [ABC470D] Inverse and Swap

zhengziyan130312 · 2026-08-10 11:16:16 · 题解

题目大意

给定一个排列 P=(P_1,\dots,P_N)，支持两种操作：

1. 1 x y：交换 P_x 和 P_y 的值。
2. 2：将 P 替换为其逆排列 P'，满足 P_{P'_i}=i。

处理完所有查询后，输出最终的 P。

操作 2 连续执行两次等于没有执行，因此我们可以用一个标记 rev 表示当前排列是否已经被“取逆数组”。同时维护两个数组：

当我们标记 rev = 0 时，当前实际排列就是 p，inv 是它的逆；当 rev = 1 时，当前实际排列就是 inv，而 p 是它的逆。

对于操作 1：

• 若 rev = 0，我们需要交换实际排列 p 中位置 x 和 y 的元素。交换后，对应的逆数组也需要更新：
  • 先交换 inv[p[x]] 和 inv[p[y]]（这两个位置分别对应交换前的两个值）；
  • 再交换 p[x] 和 p[y]。
• 若 rev = 1，同理

对于操作 2，只需取反 rev 即可。

最终输出时，根据 rev 决定输出 p 还是 inv。

时间复杂度 O(N+Q)，空间复杂度 O(N)，在题目接受范围之内。

贴代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5;
int n, q;
int p[MAXN], inv[MAXN];   // p 是排列，inv 是 p 的逆
bool rev = false;         // 标记是否取逆

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        inv[p[i]] = i;
    }

    while (q--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (!rev) {
                // 当前实际排列是 p
                swap(inv[p[x]], inv[p[y]]);  // 更新逆数组
                swap(p[x], p[y]);            // 交换 p 中的值
            } else {
                // 当前实际排列是 inv
                swap(p[inv[x]], p[inv[y]]);  // 更新 p（此时 p 作为 inv 的逆）
                swap(inv[x], inv[y]);        // 交换 inv 中的值
            }
        } else {
            rev = !rev;   // 操作2，取逆
        }
    }

    for (int i = 1; i <= n; i++) {
        if (rev) printf("%d ", inv[i]);
        else printf("%d ", p[i]);
    }
    return 0;
}

本文使用AI辅助修正格式规范
原来的数学公式写的真的令人一言难尽