CF1591D「Yet Another Sorting Problem」

1. 题目

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

Description

Petya has an array of integers a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​. 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 333-cycles. More formally, in one operation he can pick 333 pairwise distinct indices iii, jjj, and kkk (1≤i,j,k≤n1 \leq i,j,k \leq n1≤i,j,k≤n) and apply i→j→k→ii \rightarrow j \rightarrow k \rightarrow ii→j→k→i cycle to the array aaa. It simultaneously places aia_iai​ on position jjj, aja_jaj​ on position kkk, and aka_kak​ on position iii, without changing any other element.

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

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

Input

Each test contains multiple test cases. The first line contains the number of test cases ttt (1≤t≤5⋅1051 \leq t \leq 5 \cdot 10^51≤t≤5⋅105). Description of the test cases follows.

The first line of each test case contains a single integer nnn (1≤n≤5⋅1051 \leq n \leq 5 \cdot 10^51≤n≤5⋅105) — the length of the array aaa.

The second line of each test case contains nnn integers a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​ (1≤ai≤n1 \leq a_i \leq n1≤ai​≤n).

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

Output

For each test case, print "YES" (without quotes) if Petya can sort the array aaa using 333-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 666-th test case Petya can use the 333-cycle 1→3→2→11 \to 3 \to 2 \to 11→3→2→1 to sort the array.

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

2. 题解

分析

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

• 任一一个 mmm-cycle 的置换都可以改写成 m−1m-1m−1 个 222-cycle 的置换。

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

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

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

• 一种想法是计算数组 aaa 的逆序数。因为每做一次 222-cycle 的置换，逆序数就会 ±1\pm 1±1。因此，通过偶数次 222-cycle 的置换不会改变数组 aaa 的逆序数的奇偶性。所以只需要计算数组 aaa 的逆序数，然后判其奇偶性即可。计算一个数组的逆序数的最优算法有：树状数组（BIT）、CDQ 分治，时间复杂度为 O(nlog⁡n)O(n\log{n})O(nlogn)。
• 另一种想法则是直接计算数组 aaa 变成有序所需要的 222-cycle 置换次数。假定数组 aaa 变成有序后应该满足 ai=ia_i = iai​=i，即数值要等于其对应的下标。然后我们从 aia_iai​ 开始 BFS，按照 ai→aai→⋯a_i \to a_{a_i} \to \cdotsai​→aai​​→⋯，直到循环回 aia_iai​ 为止，设整个循环长度为 mmm，则这个循环即为 mmm-cycle 的置换，可转换成 m−1m-1m−1 个 222-cycle 的置换。同时我们将访问过的 aia_iai​ 全部标记上。最终，只需从头到尾遍历一遍数组 aaa 即可，对每个元素作以下判断：
  • 若 aia_iai​ 没有被标记，则从 aia_iai​ 开始 BFS 找到其所在的置换。
  • 若 aia_iai​ 被标记了，说明之前已经遍历过其所在的置换，直接跳过。

  最后，统计转换成 222-cycle 置换的所有数目，判断其奇偶性即可。不难计算得时间复杂度为 O(n)O(n)O(n)。当 aia_iai​ 的数值范围过大时，需要将 aia_iai​ 离散化（可以使用 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;
}