题解：AT_abc470_d [ABC470D] Inverse and Swap

chenyuan3 · 2026-08-10 12:04:47 · 题解

:::success[引理：对于两个排列 P 和 P'，P_{P'_i}=i 等价于 P'_{P_i}=i]

这个比较显然，因为 P_{P'_{i}}=i，所以 P'_{P_{P'_i}}=P'_i，用 i 代替 P'_i 即可得到 P'_{P_i}=i；逆命题同理，不过多赘述。

:::

操作 2 显然不能直接暴力，我们可以同时预处理 P 和 P'，那么操作 2 只需交换 P 和 P' 即可。由引理可以轻松得出做法的正确性。

然后看操作 1。交换 P_i 和 P_j 作用在 P' 上，就是交换 P'_{P_i} 和 P'_{P_j}，其中 P_i 和 P_j 均指交换前的值。

于是就可以通过此题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5e5 + 10;
ll n, q;
void solve()
{
    cin >> n >> q;
    vector<ll> p(n + 1), pp(n + 1);
    for (ll i = 1; i <= n; i++)
    {
        cin >> p[i];
        pp[p[i]] = i;
    }
    while (q--)
    {
        ll op;
        cin >> op;
        if (op == 1)
        {
            ll x, y;
            cin >> x >> y;
            ll px = p[x], py = p[y];
            swap(p[x], p[y]);
            swap(pp[px], pp[py]);
        }
        else
        {
            swap(p, pp);
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        cout << p[i] << ' ';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}