AcWing 788. 逆序对的数量
原题链接
简单
作者:
yyw233
,
2024-03-24 13:17:00
,
所有人可见
,
阅读 3
算法1
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define ll long long
#define pii pair<int,int>
#define rep(x,y,z) for(int x=y;x<=z;x++)
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
using namespace std;
const int N = 1e6+10;
ll a[N];
ll e_a[N];
int n;
ll merge_sort(ll* a,int l,int r)
{
ll sum=0;
if(r<=l) return 0;
int m=(l+r)>>1;
sum+= merge_sort(a,l,m);
sum+= merge_sort(a,m+1,r);//m+1,防止边界问题
int i=l,j=m+1,t=l;//j=m+1
while(i<=m&&j<=r)
{
if(a[i]<=a[j]) e_a[t++]=a[i++];
else e_a[t++]=a[j++],sum+=m-i+1;//逆序对数量为m-i+1
}
while(i<=m)
{
e_a[t++]=a[i++];
}
while(j<=r)
{
e_a[t++]=a[j++];
}
rep(i,l,r) a[i]=e_a[i];//复原
return sum;
}
int main ()
{
IOS
cin>>n;rep(i,1,n) cin>>a[i];
cout<<merge_sort(a,1,n);
}