传送门：洛谷 CF2244C Stepan and Permutation | Codeforces C. Stepan and Permutation
更佳的阅读体验：CF2244C 题解

简要题意：给你一个排列，你可以任意次交换下标差恰好为 $x$ 或 $y$ 的元素，判断是否能使得排列变为升序。$n \le 2 \times 10^5$。

我们可以将每个下标看作一个节点，如果两个下标之差为 $x$ 或 $y$，就在它们之间连边。此时，一次操作就是交换图中一条边两端的元素。

由此我们发现，在一个连通块内，可以沿路径不断交换，使得连通块内的元素任意排序。但任意排序仅限这个连通块内部，所以元素无法移动到其他连通块里。

那我们需要判断的就变成了，对于每个元素，它在原序列中的位置和排序后应该到达的位置是否在同一连通块内。即，是否对于原序列中的任意元素都有 $p_i$ 与 $i$ 在同一连通块内。这一过程可以借助并查集来实现。

单组数据时间复杂度 $O(n \alpha(n))$。

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

const int N = 2e5 + 10;
int t, n, x, y, p[N], fa[N], rk[N];
bool flag;

int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) fa[x] = fa[y];
    else if (rk[x] == rk[y]) fa[x] = fa[y], ++rk[y];
    else fa[y] = fa[x];
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        flag = false;
        cin >> n >> x >> y;
        for (int i = 1; i <= n; ++i) cin >> p[i];
        fill(rk + 1, rk + n + 1, 1);
        iota(fa + 1, fa + n + 1, 1);
        for (int i = 1; i <= x; ++i)
            for (int j = i; j <= n; j += x) merge(i, j);
        for (int i = 1; i <= y; ++i)
            for (int j = i; j <= n; j += y) merge(i, j);
        for (int i = 1; i <= n; ++i) if (find(i) != find(p[i])) {
            flag = true;
            break;
        } cout << (flag ? "NO\n" : "YES\n");
    } return 0;
}