逆序对题解
2025-07-25 18:28:25
发布于:浙江
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9;
int a[N],tmp[N],n;
long long ans;
void Merge(int a[],int l1,int r1,int l2,int r2){
int i = l1,j = l2;
int cnt = 0;
while(i <= r1 && j <=r2){
if(a[i]<=a[j]){
tmp[cnt++]=a[i++];
}
else{
tmp[cnt++]=a[j++];
ans+=r1-i+1;
}
}
while(i<= r1)tmp[cnt++]=a[i++];
while(j <= r2)tmp[cnt++]=a[j++];
for(int i = 0;i < cnt;i++){
a[l1+i]=tmp[i];
}
}
void MergeSort(int a[],int l,int r){
if(l>=r)return;
int mid = (l+r)/2;
MergeSort(a,l,mid);
MergeSort(a,mid+1,r);
Merge(a,l,mid,mid+1,r);
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
MergeSort(a,1,n);
cout<<ans;
}
这里空空如也
有帮助,赞一个