zyq13541255211 @ 2024-11-16 11:04:57
传送门
#include <bits/stdc++.h>
using namespace std;
long long L[100005],R[100005];
long long n,a[1000005],i,j,ans=0;
void MERGE(long long l,long long q,long long r){
long long n1=q-l+1,n2=r-q;
for(i=1;i<=n1;i++){
L[i]=a[l+i-1];
}
for(j=1;j<=n2;j++){
R[j]=a[q+j];
}
L[i]=0x3f3f3f3f;
R[i]=0x3f3f3f3f;
i=1,j=1;
for(long long k=l;k<=r;k++){
if(L[i]<=R[j]){
a[k]=L[i];
i++;
}
else{
a[k]=R[j];
j++;
ans+=n1-i+1;
}
}
return ;
}
void MERGE_SORT(long long l,long long r){
if(l<r){
long long q=(l+r)/2;
MERGE_SORT(l,q);
MERGE_SORT(q+1,r);
MERGE(l,q,r);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie();
cin>>n;
for(long long qq=0;qq<n;qq++){
cin>>a[qq];
}
MERGE_SORT(0,n-1);
cout<<ans;
return 0;
}