CF1591D Yet Another Sorting Problem（奇偶排列）
逆序数为偶数称为偶排列，逆序数为奇数称为奇排列
交换一个序列中两个不同的数会使这个序列的逆序对的个数改变奇数个（改变为 +1或 -1）
而题目的这种操作就等于连续进行两次交换操作，逆序数的改变是偶数个（改变为 -2 或 0 或 +2）
而排好序的逆序数是0个，所以当逆序数为偶数个时，则能成功
当序列中有相同的数时，则可以看作能任意两个数进行交换操作，而此时逆序数的改变是+1（或 -1），所以能成功
二维偏序问题，要想到二维映射、逆序对、树状数组等
而题目的这种操作就等于连续进行两次交换操作，逆序数的改变是偶数个（改变为 -2 或 0 或 +2）
而排好序的逆序数是0个，所以当逆序数为偶数个时，则能成功
当序列中有相同的数时，则可以看作能任意两个数进行交换操作，而此时逆序数的改变是+1（或 -1），所以能成功
二维偏序问题，要想到二维映射、逆序对、树状数组等
#include<bits/stdc++.h>
using namespace std;
#define low(x) (x&(-x))
#define ll long long
int const M=1e5+7;
int const N=5e5+7;
int t,n;
int a[N],tr[N];
void add(int p,int w){
for(;p<=n;p+=low(p)){
tr[p]+=w;
}
}
ll ask(int p){
ll res=0;
for(;p>=1;p-=low(p)){
res+=tr[p];
}
return res;
}
int main(){
cin >> t;
while(t--){
cin >> n;
int fg=0;ll res=0;
for(int i=1,x;i<=n;++i){
cin >> x;
if(fg) continue;
if(!fg&&ask(x)-ask(x-1)) fg=1;
ll z=i-ask(x)-1;
add(x,1);
res+=z;
}
if(fg || res%2==0) cout << "YES\n";
else cout << "NO\n";
for(int i=0;i<=n;++i) tr[i]=0;
}
return 0;
}
投递小米集团等公司10个岗位