AcWing 788. 逆序对的数量
原题链接
简单
作者:
ls131
,
2021-07-31 00:22:07
,
所有人可见
,
阅读 188
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N =1e5+10;
int n,m;
int T;
int a[N];
int tmp[N];
LL merge_sort(int a[],int l,int r)
{
//WA3 RETURN 0
if(l>=r) return 0; //递归函数写出口 到最后单个数直接 返回
int mid=l+r>>1;
int i=l,j=mid+1; //归并的双指针指向双段头
//int mid=l+r>>1;
LL res=merge_sort(a,l,mid)+merge_sort(a,mid+1,r);
int k=0;//记录辅助数组的延伸长度
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) tmp[k++]=a[i++]; //WA1 =
else
{
res+=mid-i+1;
tmp[k++]=a[j++];
}
}
while(i<=mid) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
for(int i=l,j=0;i<=r;i++) a[i]=tmp[j++]; //WA2 =
return res;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int ans=merge_sort(a,0,n-1);
cout<<ans<<endl;
return 0;
}