$\it{***方法一(己)***}$
思路
经分析逆序对的数量等于每层归并排序每次纳入右侧数组排好序的元素时,左侧数组排好序的剩余暂未纳入的元素个数累和
要点
1.记录逆序对数量要用longlong
类型,以免爆范围
2.if(q[i]<=q[j]) tmp[k++]=q[i++];
,判断条件要写成$\leqslant$,使左右两数组中有相同的数
的时候,先排左边
的,这样就能确保当纳入右边的数时,一定和左边剩余的数构成逆序对
3.左侧数组中剩余暂未纳入元素个数=mid-i+1
代码
#include<bits/stdc++.h>
using namespace std;
int q[100010];
int tmp[100010];
int n;
//记录逆序对的个数
long long int num=0;
void merge_sort(int q[],int l,int r)
{
if(l>=r) return;
int mid=l+r>>1;
merge_sort(q,l,mid),merge_sort(q,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++];
//排序中途纳入右侧数组的数,该数与左侧数组剩余的数一定构成逆序对
//左侧数组剩余的数个数为:mid-i+1
else num=num+(mid-i+1),tmp[k++]=q[j++];
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(i=l,k=0;i<=r;) q[i++]=tmp[k++];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
cin>>q[i];
merge_sort(q,0,n-1);
cout<<num<<endl;
return 0;
}