题解

其实这道题比C简单，早知道先做D了，也没用什么算法，就按着题目说的做就行，就是要用容器存，容器整个$swap$复杂度是$O(1)$

#include<iostream>
#include<vector>
using namespace std;
int n,q;
int main(){
    cin>>n>>q;
    vector<int>p(n+1,0);
    vector<int>inv(n+1,0);//这就是P'
    for(int i=1;i<=n;i++){
        cin>>p[i];
        inv[p[i]]=i;
    }
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            int a=p[x],b=p[y];
            swap(p[x],p[y]);
            //交换后inv也要交换
            inv[a]=y;
            inv[b]=x;
        }else{
            swap(p,inv);//容器可以直接交换，且复杂度是O(1)
        }
    }
    for(int i=1;i<=n;i++)
        cout<<p[i]<<" ";
    return 0;
}