ABC470 D 题解

wcqk · 2026-08-09 09:38:10 · 题解

读完题之后，个人的感觉认为操作 2 是需要思考的操作，操作 1 简单的交换即可。

我们手玩样例之后容易发现，如果操作 2 进行奇数次，那么就等于进行了 1 次操作 2，如果进行了偶数次操作 2，那么就等于没有进行操作 2。

::::success[简单证明] 设当前排列为 P，操作 2 将其变为逆排列 P^{-1}。

由逆排列的定义可知：

因此连续执行两次操作 2 等价于不变：

所以：

• 执行偶数次操作 2：(P^{-1})^{\text{2k}}=P，相当于没有操作
• 执行奇数次操作 2：(P^{-1})^{\text{2k-1}}=P^{-1}，相当于执行一次操作 2

（k 为正整数） ::::

故只需记录操作 2 出现次数的奇偶性即可。

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

int arr[500010],p[500010];
int n,q;
void solve(){
    cin>>n>>q;

    for(int i=1;i<=n;i++){
        cin>>arr[i];
        p[arr[i]]=i;
    }

    int now=0;

    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            if(now==0){
                int a=arr[x],b=arr[y];
                swap(arr[x],arr[y]);
                swap(p[a],p[b]);
            }else{
                int a=p[x],b=p[y];
                swap(p[x],p[y]);
                swap(arr[a],arr[b]);
            }
        }if(op==2){
            if(now==0)now=1;
            else now=0;
        }
    }

    if(now==0){
        for(int i=1;i<=n;i++){
            cout<<arr[i]<<' ';
        }
    }else{
        for(int i=1;i<=n;i++){
            cout<<p[i]<<' ';
        }
    }
}
int main(){
    solve();
}

输入 O(n)，操作 O(1)，输出 O(n)。对于 n\leq 5 \times 10^5 来说这个复杂度非常肥美，显然可以通过。