随机排列
https://www.acwing.com/activity/content/problem/content/9631/
我找到的关于逆序对的一个应用
可以证明的结论是:交换两个数,必然改变一个序列的逆序对数量的
奇偶性。
证明:当交换两个相邻的数时,逆序对数目+1或-1
当交换的两个数不相邻时,不妨设要将a,b交换,其下标为i,j
可以先将a换到下标为j-1的位置,此时交换a,b
这样一来,b在下标为j-1的位置,a在下标为j的位置
然后用类似的技巧把b换到下标为i的地方。
这样一共进行了奇数次操作,每次操作都要改变序列逆序对数目的奇偶性,因此,总体操作一定改变序列逆序对数目的奇偶性。
另外:要复习用分治法求解一个序列的逆序对。
假设你有一个递归函数,它的目的就是求出一个序列的逆序对,顺便排序,那么,先利用这个函数求出左半边和右半边的逆序对,然后在合并序列的过程中,求出合并时产生的逆序对即可
#include<iostream>
using namespace std;
int n;
const int maxn=1e6+10;
int a[maxn];
long long int ans=0;
long long int merge_sort(int l,int r){
if(l==r) return 0;
int mid=(l+r)>>1;
long long int num1=merge_sort(l,mid);
long long int num2=merge_sort(mid+1,r);
int t1=l;int t2=mid+1;
int temp[maxn];
int tt=0;
long long int num3=0;
while(t1<=mid&&t2<=r){
if(a[t1]<=a[t2]){
temp[++tt]=a[t1++];
}
else{
num3+=mid-t1+1;
temp[++tt]=a[t2++];
}
}
while(t1<=mid){
temp[++tt]=a[t1++];
}
while(t2<=r){
temp[++tt]=a[t2++];
}
for(int i=1;i<=tt;i++){
a[i+l-1]=temp[i];
}
return num1+num2+num3;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
ans=merge_sort(1,n);
if(n%2==0){
if(ans%2==0) cout<<1;
else cout<<2;
}
else{
if(ans%2==1) cout<<1;
else cout<<2;
}
return 0;
}