1. 题目

题目链接:CF1591D「Yet Another Sorting Problem」

Description

Petya has an array of integers a1,a2,,ana_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 33-cycles. More formally, in one operation he can pick 33 pairwise distinct indices ii, jj, and kk (1i,j,kn1 \leq i,j,k \leq n) and apply ijkii \rightarrow j \rightarrow k \rightarrow i cycle to the array aa. It simultaneously places aia_i on position jj, aja_j on position kk, and aka_k on position ii, without changing any other element.

For example, if aa is [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=5, then the array becomes [50,40,20,30,10,60][\underline{50},\underline{40},20,30,\underline{10},60].

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

Input

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

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

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ain1 \leq a_i \leq n).

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

Output

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

Example

input #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

1
2
3
4
5
6
7
YES
YES
NO
YES
NO
YES
YES

Note

In the 66-th test case Petya can use the 33-cycle 13211 \to 3 \to 2 \to 1 to sort the array.

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

2. 题解

分析

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

  • 任一一个 mm-cycle 的置换都可以改写成 m1m-122-cycle 的置换。

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

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

对于数组 aa 中元素各不相同的情况,有两种思路:

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

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

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

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

代码

BIT 计算逆序数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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;
}

置换的奇偶性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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;
}