题解：AT_abc470_d [ABC470D] Inverse and Swap

ryf2011 · 2026-08-10 08:25:52 · 题解

注意到，几乎所有题目都可以通过若干个“注意到”来解决，本题更是如此。

1. 题目思路

注意到，排列 P' 实际上可以看作排列 P 的“指针”，具体来讲，排列 P' 的 P'_i 代表排列 P 中元素 i 所在下标（假设下标从 1 开始）。

注意到，本题暴力复杂度过高。我们先考虑没有操作 1 怎样做。

我们来考虑操作 2 如何优化。注意到一条关键性质：若没有操作 1，操作 2 只可能在排列 P 和 P' 中来回交换。这条性质很好理解，因为排列 P 和 P' 其实可以看作是互为“指针”的关系，即对于排列 P，排列 P' 是它的“指针”，反之同理。

注意到，此时对于操作 1 我们可以同时维护排列 P 以及它的“指针”，当 P_x,P_y 发生交换时，对应的 P'_{P_x},P'_{P_y} 就要交换，反之同理。

注意到，此时对于操作 2 我们可以维护一个布尔变量，表示当前操作的排列是否为 P，每执行一次操作 2 就对该变量取反（即 true 和 false 互换）。操作 1 的时候判断一下对哪个排列进行交换就好。

我们利用了五个“注意到”完美解决了本题。

2. 代码

注：代码仅供参考。

#include<bits/stdc++.h>
using namespace std;
const int max_n=5e5+2;
int n,q,p[max_n],op,x,y;
int z[max_n];
bool printp; //是否输出原数组 
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
int main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++){
        p[i]=read();
        z[p[i]]=i;
    }
    printp=true;
    for(int i=1;i<=q;i++){
        op=read();
        if(op==1){
            x=read(),y=read();
            if(printp){
                z[p[x]]=y,z[p[y]]=x;
                swap(p[x],p[y]);    
            }
            else{
                p[z[x]]=y,p[z[y]]=x;
                swap(z[x],z[y]);
            }
        }
        else{
            printp=!printp; //取反
        }
    }
    if(printp){
        for(int i=1;i<=n;i++){
            printf("%d ",p[i]);
        }
        puts("");
    }
    else{
        for(int i=1;i<=n;i++){
            printf("%d ",z[i]);
        }
        puts("");
    }
    return 0;
}