皇族鬼圣 @ 2022-10-03 10:13:12
#include<iostream>
using namespace std;
int a[500005],b[500005];
long long ans=0;
void mergesort(int l, int r)
{
if(l>=r)
return;
int mid = (l+r)>>1;
mergesort(l, mid);
mergesort(mid+1, r);
int left[50005], right[50005];
int lth1 = mid - l + 1, lth2 = r - mid;
for(int i=1;i<=lth1;i++)
left[i] = a[l+i-1];
for(int i=1;i<=lth2;i++)
right[i] = a[mid+i];
int i = 1, j = 1;
int k = l;
while(i<=lth1 && j<=lth2)
{
if(left[i]<right[j])
a[k++] = left[i++];
else
{
a[k++] = right[j++];
ans+=mid-l+1;
}
}
while(i<=lth1)
a[k++] = left[i++];
while(j<=lth2)
a[k++] = right[j++];
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
mergesort(0, n-1);
cout<<ans;
return 0;
}by zhangjingxing2012 @ 2022-10-04 14:06:10
#include<bits/stdc++.h>
using namespace std;
long long ans;
int a[500010],r[500010];
void msort(int s,int t)
{
if(s==t) return;//如果只有一个数字，那么无需排序
int mid=(s+t)/2;
msort(s,mid);//分解左序列
msort(mid+1,t);//分解右序列
int i=s,j=mid+1,k=s;//接下来合并
while(i<=mid&&j<=t)
{
if(a[i]<=a[j])
{
r[k]=a[i];k++;i++;
}
else {
r[k]=a[j];k++;j++;
ans+=mid-i+1;//统计逆序对数量
}
}
while(i<=mid)//复制左边子序列剩余
{
r[k]=a[i];k++;i++;
}
while(j<=t)//复制右边子序列剩余
{
r[k]=a[j];k++;j++;
}
for(int i=s;i<=t;i++) a[i]=r[i];
return;
}
int main()
{
ios::sync_with_stdio(false);//加快cin的读入速度
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
msort(1,n);
printf("%lld",ans);
}