D - Yet Another Sorting Problem

一段长度为n的序列。每次可以选择一个三元组 $(i, j, k)$，然后将 $a_i, a_j,a_k$ 三个数环形交换。即：$a_j=a_i,a_k=a_j,a_i=a_k$

判断是否通过这样的操作（次数不限）使得序列有序

当$(a_i,a_j,a_k)$三个数两两不相等时，我们发现，无论执行多少次这样的操作，逆序数只会改变0或2。

当$(a_i,a_j,a_k)$存在两个数相等时，逆序数可以改变1（也可以改变2）。

因此我们这样判断：如果逆序数%2==0，说明可以使逆序数变为0，即单调非降。

特别的，如果存在两个数相等，那么奇偶性就可以任意改变，故也可以使序列有序。

其余情况为NO。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline void read(int &a) {a=0;int c=getchar(); while(c>'9'||c<'0') c=getchar(); while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar(); }
const int N=5e5+5;
int n,c[N],rk[N], t;
int ans;
struct node
{
	int id,w;
	bool operator < (const node &b) const
	{
		return w==b.w?id<b.id:w<b.w;
	}
}a[N];
inline void insert(int x,int w)
{
	for(;x<=n;x+=x&-x) c[x]+=w;
}
inline int query(int x)
{
	int sum=0;
	for(;x;x-=x&-x) sum+=c[x];
	return sum;
}
signed main()
{
	read(t);
	while(t--)
	{
		ans = 0;
		read(n);
		for(int i=1;i<=n;i++) read(a[i].w),a[i].id=i;
		sort(a+1,a+1+n);
		bool flag = 0;
		for(int i = 2; i <= n; i++)
		{
			if(a[i].w == a[i - 1].w) {flag = 1; break;}
		}
		if(flag) {puts("YES"); continue;}
		for(int i=1;i<=n;i++) rk[a[i].id]=i;
		for(int i=1;i<=n;i++)
		{
			insert(rk[i],1);
			ans += i - query(rk[i]);
		}
		if(ans & 1) puts("NO");
		else puts("YES");
		for(int i = 0; i <= n; i++) c[i] = rk[i] = 0;
	}
	return 0;
}