Yatsuha @ 2024-01-26 00:16:58
#define _CRT_SECURE_NO_WARNINGS 1;
#include<cstdio>
using namespace std;
int n, arr[2][500000], flag = 0;
long long sum = 0;
void sort(int, int, int, int);
void mergesort();
int main() {
scanf("%d", &n);
int i;
for (i = 0; i < n; i++) scanf("%d", &arr[0][i]);
for (i = n; i < 500000; i++) arr[0][i] = arr[1][i] = 0x3f3f3f3f;
mergesort();
printf("%lld", sum);
return 0;
}
void sort(int arr1, int arr2, int n1, int n2) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr[flag][arr1 + i] > arr[flag][arr2 + j]) {
arr[(flag + 1) % 2][arr1 + k] = arr[flag][arr1 + i];
k++;
sum += (long long)(n2 - j);
i++;
}
if (arr[flag][arr1 + i] <= arr[flag][arr2 + j]) {
arr[(flag + 1) % 2][arr1 + k] = arr[flag][arr2 + j];
k++;
j++;
}
}
if (i == n1) {
while (j < n2) {
arr[(flag + 1) % 2][arr1 + k] = arr[flag][arr2 + j];
j++;
k++;
}
}
else {
while (i < n1) {
arr[(flag + 1) % 2][arr1 + k] = arr[flag][arr1 + i];
i++;
k++;
}
}
}
void mergesort() {
int l, i;
for (l = 1;l < n - 1; l *= 2) {
for (i = 0; i <= n - 2 * l; i += 2 * l) {
sort(i, i + l, l, l);
}
sort(i, i + l, l, n - i - l);
flag = (flag + 1) % 2;
}
}by timmyliao @ 2024-01-26 08:29:09
AC
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAX = 500005 ;
int n ;
LL a[MAX] ;
LL b[MAX] ;
LL ans = 0 ;
void merge_sort(int l ,int r ){
if(l ==r )return ;
LL mid = (l+r)/2 ;
merge_sort(l,mid) ;
merge_sort(mid+1,r) ;
int i = l , k = l , j =mid +1 ;
while(i<=mid && j<=r){
if(a[i]<=a[j])
b[k++] =a[i++];
else{
b[k++] =a[j++] ;
ans+=mid-i+1 ;
}
}
while(i<=mid){
b[k++] =a[i++] ;
}
while(j<=r){
b[k++] =a[j++];
}
for(int i = l; i<=r ; i++){
a[i] = b[i] ;
}
}
int main(){
scanf("%d",&n);
for(int i = 1 ; i<=n ; i++ ){
scanf("%lld",&a[i]);
}
merge_sort(1,n) ;
cout<<ans;
return 0 ;
}by Yatsuha @ 2024-01-26 09:21:37
@timmyliao 感谢大佬，可能是我归并排序那部分写的有点问题