#include<iostream>
using namespace std;
typedef long long LL;
const int N=100010;
int n;
int q[N];
int tmp[N];
LL merge_sort(int l,int r){
if(l>=r) return 0;
int mid=l+r >>1; //向下取整
LL res=merge_sort(l,mid)+merge(mid+1,r);
//归并的过程
int k=0;i=l,j=mid+1;
while(i<=mid&&j<=r){
if(q[i]<q[j]) tmp[k++]=q[i++];
else{
tmp[k++]=q[j++];
res=mid-i+1;
}
}
//扫尾
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
//物归原主
for(i=0,j=l;j<=r;i++,j++) q[j]=tmp[i];
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>q[i];
cout<<merge_sort(0,n-1)<<endl;
return 0;
}
tips:
1.为什么要物归原主?排好序的数组是存储在tmp中的,把tmp中的有序数组移回到q中才能利用公式res=mid-i+1
2.左右半边的元素在各自任意调换顺序,是不影响第三步计数的,因此我们可以数完就给它排序。这么做的好处在于,如果序列是有序的,会让第三步计数很容易
3.本质上只存在一个在左一个在右的情况?因为最后会分成两个数的区间,就都可以用mid-l+1来计算逆序对个数
- 先假定归并排序把序列进行排序并返回逆序对的数量。
- 然后当两个数在左边或者右边的时候就是直接调用归并排序返回。
- 当出现一个在左,一个在右的时候,就是第三种情况,利用多路归并算法进行求解。
- 而前面两种由于递归的性质最后都会变成第三种情况。