I caught the sparkle in my mind and got AC1 ! It is a great great experience !
So the basic idea: permute on 3 consecutive items doesn‘t change the parity of the no. of inversions. Each permutation can only remove 0 or 2 inversions. So we say "YES" when no. of inversion % 2 = = 0. And we use MergeSort to count it in O(nlgn).
ret = 0 def merge(arr1, arr2): global ret if not arr1: return arr2 if not arr2: return arr1 for v2 in arr2: arr1.append(v2) i = len(arr1) - 1 while(i > 0): if arr1[i] < arr1[i - 1]: arr1[i - 1],arr1[i] = arr1[i], arr1[i - 1] i -= 1 ret += 1 else: break return arr1 def mergeSort(arr): n = len(arr) if (n < 2): return arr return merge(mergeSort(arr[:n//2]), mergeSort(arr[n//2:])) ### t = int(input()) for _ in range(t): n = int(input()) arr = list(map(int, input().split())) ret = 0 mergeSort(arr) print("YES" if ret % 2 == 0 else "NO")
原文：http://www.cnblogs.com/tonix/p/5385419.html