D. Yet Another Sorting Problem

​​傳送門​​

題意：

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define pb push_back
const int mod = 1e9+7;
int d[500010];
int lowbit(int x)
{
  return x&(-x);
}
int n;
void add(int idx)
{
  while(idx>0)d[idx]++,idx-=lowbit(idx);
}
int ask(int idx)
{
  int sum = 0;
  while(idx<=n)sum+=d[idx],idx+=lowbit(idx);
  return sum;
}
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    cin>>n;
    vector<int>a(n+10,0),vis(n+10,0);
    int flag = 0;
    for(int i = 1; i <= n; i++)
    {
      cin>>a[i],vis[a[i]]++;
      if(vis[a[i]]==2)flag = 1;
    }
    if(flag)cout<<"YES\n";
    else
    {
      ll ans = 0;
      for(int i = 1; i <= n; i++)
      {
        ans+=ask(a[i]);
        add(a[i]);
      }
      if(ans%2)cout<<"NO\n";
      else cout<<"YES\n";
      for(int i = 1; i <= n; i++)d[i] = 0;
    }
    
  }
}