308858: CF1585D. Yet Another Sorting Problem
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Yet Another Sorting Problem
题意翻译
我有一个 $n$ 元序列 $\{a_n\}$,希望通过轮换三元组的方式给序列排序. 每次操作挑出序列中的三个互异下标 $1\leq i,j,k\leq n$ 并轮换循环 $i→j→k→i$,即给序列的位置 $j,k,i$ 同时赋上值 $a_i,a_j,a_k$. 给定 $\{a_n\}$,请判断是否能经过 $\geq0$ 次这种操作将其排为非降序. 输入的第一行是测试用例数 $t∈[1,10^5]$. 每个测试用例的第一行是序列长度 $n∈[1,10^5]$;第二行是 $n$ 个元素 $a_i$,$i,a_i∈[1,n]$. 所有的 $n$ 之和不超过 $10^5$. 对每个测试用例,若可以排序输出一行 ``YES``,否则输出一行 ``NO``,不区分大小写.题目描述
Petya has an array of integers $ a_1, a_2, \ldots, 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 \to j \to k \to 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.输入输出格式
输入格式
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 $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .
输出格式
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).
输入输出样例
输入样例 #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
输出样例 #1
YES
YES
NO
YES
NO
YES
YES