题解：AT_abc470_d [ABC470D] Inverse and Swap

· · 题解

个人感觉难度不如 C。

题意

有一个长度为 n 的排列 P，有一个空序列 A。支持两种操作。

  1. 交换 P_x 和 P_y
  2. 把 P 变成 P 的逆排列。对于任意 i \in [1,n]，先 A_{P_i} \rightarrow i，然后把 P \rightarrow A。

思路

手玩一下可以发现，逆排列的逆排列是本身，且交换两个值过后做一次你排列等价于先做逆排列然后交换。所以我们可以把所有的交换操作移到最前面，先全部交换完，在记录操作二的个数。如果是奇数就变成逆排列，否则不变。

:::info[code]

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e5 + 5;
int a[N],pos[N];
int n,q;
bool fp = 0;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        pos[a[i]] = i;
    }
    while(q--){
        int x;
        cin >> x;
        if(x == 1){
            int l,r;
            cin >> l >> r;
            if(!fp){
                int vl = a[l],vr = a[r];
                swap(a[l],a[r]);
                pos[vl] = r;
                pos[vr] = l;
            }else{
                int psl = pos[l],psr = pos[r];
                swap(pos[l],pos[r]);
                a[psl] = r;
                a[psr] = l;
            }
        }else{
            fp = !fp;
        }
    }
    if(fp){
        for(int i = 1;i <= n;i++){
            cout << pos[i] << " ";
        }
    }else{
        for(int i = 1;i <= n;i++){
            cout << a[i] << " ";
        }
    }
    return 0;
}

::::