这是我第一次的逆序对,但感觉没什么错误,请各位帮我大佬康康
代码如下:
#include<bits/stdc++.h>
using namespace std;
long long n,s1[500050],s2[500020],cnt;
void merge(int L,int R,int Mid){
long long i = L,j = Mid + 1,k = L;
while(i <= Mid && j <= R){
if(s1[i] <= s1[j])s2[k ++]=s1[i ++];
else{
cnt += Mid - i + 1;
s2[k ++] = s1[j ++];
}
}
while(i <= Mid)s2[k ++] = s1[i ++];
while(j <= R)s2[k ++] = s1[j ++];
for(int i=L; i<=R; i++)s1[i] = s2[i];
}
void mergesort(int L,int R){
if(L<R){
long long Mid = (L + R) / 2;
mergesort(1,Mid);mergesort(Mid+1,R);
merge(L,R,Mid);
}
}
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++)scanf("%d",&s1[i]);
mergesort(1,n);
printf("%d ",cnt);
return 0;
}