题解：AT_abc470_d [ABC470D] Inverse and Swap

Berd__ · 2026-08-10 08:24:49 · 题解

[ABC470D] Inverse and Swap

首先来看一下题目大意。

给你一个排列 P，每次有以下操作：

• 交换当前排列中的第 x 项和第 y 项。
• 对于所有的 1\le i \le N，把 P_{P_i} 替换为 i。

手模一下样例，你发现如果只进行第二种操作，我们只关心这种操作进行次数的奇偶性，因为第二种操作连续进行 2 次后对原排列没有影响。

所以，考虑记录两个排列 P_1 和 P_2，分别表示原排列和在原排列上进行一次第二种操作后的排列，这样我们就解决了只有第二种操作的情形。（也就是，第二种操作进行偶数次时输出 P_1，进行奇数次时输出 P_2）

接下来考虑解决加入第一种交换操作时，如何维护 P_1 和 P_2。

再次手模，以排列 3 4 5 2 1 为例，刚开始时：

P1=3 4 5 2 1
P2=5 4 1 2 3

若此时交换第 1 和第 3 个位置，我们发现：

P1=5 4 3 2 1 //(5和3交换了)
P2=5 4 3 2 1 //(第5个位置和第3个位置上的数交换了)

因为 P_{1_i} 影响的是 P_2 的第 P_{1_i} 项，所以，若当前进行了偶数次第二种操作，此时若进行第一种操作，我们就需要交换 P_1 的第 x 和第 y 个数，并交换 P_2 的第 P_{1_x} 和 P_{1_y} 个数。

若当前进行了奇数次操作也是同样的做法。

::::info[AC Code]

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,q;
int p[500005][2];
int op,x,y;
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>p[i][0];
    for(int i=1;i<=n;i++) p[p[i][0]][1]=i;
    bool cur=0;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x>>y;
            swap(p[x][cur],p[y][cur]);
            swap(p[p[x][cur]][cur^1],p[p[y][cur]][cur^1]);
        }
        else cur^=1;
    }
    for(int i=1;i<=n;i++) cout<<p[i][cur]<<" ";
    return 0;
}

::::