AcWing 788. 逆序对的数量
原题链接
简单
作者:
aqua_
,
2024-02-26 19:58:33
,
所有人可见
,
阅读 20
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
typedef long long LL;
int a[N],tmp[N];
LL merge_sort(int q[],int l,int r){
if(l >= r){
return 0;
}
int mid = l + r >> 1;
LL res = merge_sort(q,l,mid) + merge_sort(q,mid + 1,r);
int k = 0,i = l,j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]){
tmp[k ++ ] = q[i ++ ];
}
else{
tmp[k ++ ] = q[j ++ ];
res += mid - i + 1;
}
}
while(i <= mid){
tmp[k ++ ] = q[i ++ ];
}
while(j <= r){
tmp[k ++ ] = q[j ++ ];
}
for(i = l,j = 0;i <= r;i ++ ,j ++ ){
q[i] = tmp[j];
}
return res;
}
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i ++ ){
cin >> a[i];
}
cout << merge_sort(a, 0, n - 1);
return 0;
}