CF1591D「Yet Another Sorting Problem」

1. 题目

题目链接：CF1591D「Yet Another Sorting Problem」。

Description

Petya has an array of integers $a_1,a_2,…,a_n$. He only likes sorted arrays. Unfortunately, the given array could be arbitrary, so Petya wants to sort it.

Petya likes to challenge himself, so he wants to sort array using only $3$-cycles. More formally, in one operation he can pick $3$ pairwise distinct indices $i$, $j$, and $k$ ($1 \leq i,j,k \leq n$) and apply $i \rightarrow j \rightarrow k \rightarrow i$ cycle to the array $a$. It simultaneously places $a_i$ on position $j$, $a_j$ on position $k$, and $a_k$ on position $i$, without changing any other element.

For example, if $a$ is $[10,50,20,30,40,60]$ and he chooses $i=2, j=1, k=5$, then the array becomes $[\underline{50},\underline{40},20,30,\underline{10},60]$.

Petya can apply arbitrary number of $3$-cycles (possibly, zero). You are to determine if Petya can sort his array $a$, i. e. make it non-decreasing.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 5 \cdot 10^5$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$).

It is guaranteed that the sum of nnn over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, print "YES" (without quotes) if Petya can sort the array $a$ using $3$-cycles, and "NO" (without quotes) otherwise. You can print each letter in any case (upper or lower).

Example

input #1

7
1
1
2
2 2
2
2 1
3
1 2 3
3
2 1 3
3
3 1 2
4
2 1 4 3

output #1

YES
YES
NO
YES
NO
YES
YES

Note

In the $6$-th test case Petya can use the $3$-cycle $1 \to 3 \to 2 \to 1$ to sort the array.

In the $7$-th test case Petya can apply $1 \to 3 \to 2 \to 1$ and make $a = [1, 4, 2, 3]$. Then he can apply $2 \to 4 \to 3 \to 2$ and finally sort the array.

2. 题解

分析

根据置换群相关的知识可知：

• 任一一个 $m$-cycle 的置换都可以改写成 $m-1$ 个 $2$-cycle 的置换。

以 $(3,1,2)$ 为例：在右结合的情况下 $(3, 1, 2) = (1, 3)(2, 3)$。因此，数组 $a$ 通过 $3$-cycle 的置换能够变成单调递增，则等价于数组 $a$ 通过偶数次 $2$-cycle 的置换能变成单调递增。

这里需要注意的一点是，题目没有说数组 $a$ 中的元素是各不相同的，因此需要考虑到有相同元素的情况。一旦出现相同元素，则总是能够通过偶数次 $2$-cycle 的置换将数组 $a$ 变成单调递增的。比如 $[2, 2, 3]$ 经过置换 $(1, 2)(2, 3)$ 变成 $[2, 3, 2]$，即一旦出现相同元素，则可以一步一步移动任一一个元素，最终实现数组 $a$ 有序。

对于数组 $a$ 中元素各不相同的情况，有两种思路：

• 一种想法是计算数组 $a$ 的逆序数。因为每做一次 $2$-cycle 的置换，逆序数就会 $\pm 1$。因此，通过偶数次 $2$-cycle 的置换不会改变数组 $a$ 的逆序数的奇偶性。所以只需要计算数组 $a$ 的逆序数，然后判其奇偶性即可。计算一个数组的逆序数的最优算法有：树状数组（BIT）、CDQ 分治，时间复杂度为 $O(n\log{n})$。

• 另一种想法则是直接计算数组 $a$ 变成有序所需要的 $2$-cycle 置换次数。假定数组 $a$ 变成有序后应该满足 $a_i = i$，即数值要等于其对应的下标。然后我们从 $a_i$ 开始 BFS，按照 $a_i \to a_{a_i} \to \cdots$，直到循环回 $a_i$ 为止，设整个循环长度为 $m$，则这个循环即为 $m$-cycle 的置换，可转换成 $m-1$ 个 $2$-cycle 的置换。同时我们将访问过的 $a_i$ 全部标记上。最终，只需从头到尾遍历一遍数组 $a$ 即可，对每个元素作以下判断：

  • 若 $a_i$ 没有被标记，则从 $a_i$ 开始 BFS 找到其所在的置换。
  • 若 $a_i$ 被标记了，说明之前已经遍历过其所在的置换，直接跳过。

  最后，统计转换成 $2$-cycle 置换的所有数目，判断其奇偶性即可。不难计算得时间复杂度为 $O(n)$。当 $a_i$ 的数值范围过大时，需要将 $a_i$ 离散化（可以使用 unordered_map 数据结构）。

代码

BIT 计算逆序数

#include <bits/stdc++.h>
#define ll int
#define il inline
#define MAXN 500005

using namespace std;

//lowbit
il ll lowbit(ll x) {
    return x & -x;
}

//update
il void update(ll x, ll cnt, ll *ans) {
    while(x <= cnt) {
        ++ans[x];
        x += lowbit(x);
    }
}

//query
il ll query(ll x, ll *ans) {
    ll result = 0;
    while(x > 0) {
        result += ans[x];
        x -= lowbit(x);
    }
    return result;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t;
    cin >> t;
    ll a[MAXN] = {0}, b[MAXN] = {0}, ans[MAXN] = {0};
    for(ll i = 0; i < t; ++i) {
        ll cnt = 0;
        ll n;
        cin >> n;
        for(ll j = 1; j <= n; ++j) {
            cin >> a[j];
            b[j] = a[j];
        }
        memset(ans, 0, sizeof(ll)*(n+2));
        std::sort(b+1,b+n+1);
        // 是否有相同元素
        ll ok = 0;
        for(ll j = 2; j <= n; ++j) {
            if(b[j] == b[j-1]) {
                ok = 1;
                break;
            }
        }
        // 离散化序列
        ll res = 0;
        cnt = std::unique(b+1,b+n+1)-b-1;
        for(ll j = 1; j <= n; ++j) {
            ll x = std::lower_bound(b+1, b+cnt+1, a[j])-b;
            update(x, cnt, ans);
            res += j - query(x, ans);
        }
        if(res % 2) {
            if(ok) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        } else {
            printf("YES\n");
        }
    }
    return 0;
}

置换的奇偶性

#include <bits/stdc++.h>
#define ll int
#define il inline
#define MAXN 500005

using namespace std;

//快读
il ll read() {
    char ch = getchar();
    ll ans = 0;
    while(ch < '0' || ch > '9') {
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        ans = (ans<<1) + (ans<<3) + (ch-'0');
        ch = getchar();
    }
    return ans;
}


int main()
{
    ll t;
    t = read();
    ll a[MAXN] = {0}, b[MAXN] = {0};
    for(ll i = 0; i < t; ++i) {
        ll cnt = 0;
        ll n, ok = 0;
        n = read();
        memset(b, 0, sizeof(ll)*(n+2));
        for(ll j = 1; j <= n; ++j) {
            a[j] = read();
            b[a[j]] += 1;
            if(b[a[j]] > 1) {
                ok = 1;
            }
        }
        if(ok) {
            printf("YES\n");
        } else {
            ll res = 0;
            memset(b, 0, sizeof(ll)*(n+2));
            for(ll j = 1; j <= n; ++j) {
                ll idx = j;
                ll ans = 0;
                while(!b[a[idx]]) {
                    b[a[idx]] = 1;
                    ans += 1;
                    idx = a[idx];
                }
                res += ans ? ans-1 : 0;
            }
            if(res % 2) {
                printf("NO\n");
            } else {
                printf("YES\n");
            }
        }
    }
    return 0;
}