题解

额好像把数组倒过来求逆序对也行（？

#include <iostream>
#include <cstdio>
using namespace std;
int a[500005], arr[500005];
long long ct;
int read(){
	char c = getchar();
	int x = 0;
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}return x;
}void merge(int *a, int left, int mid, int right){
	int i = left, j = mid + 1, ctt = left;
	while(i <= mid && j <= right){
		if(a[i] <= a[j]) arr[ctt++] = a[i++];
		else{
			arr[ctt++] = a[j++];
			ct += mid - i + 1;
		}
	}while(i <= mid) arr[ctt++] = a[i++];
	while(j <= right) arr[ctt++] = a[j++];
	for(int i = left; i <= right; i++){
		a[i] = arr[i];
	}
}void mergesort(int *a, int left, int right){
	if(left >= right) return;
	int mid = (left + right) / 2;
	mergesort(a, left, mid);
	mergesort(a, mid + 1, right);
	merge(a, left, mid, right);
}
int main(){
	int n = read();
	for(int i = 1; i <= n; i++) a[n - i + 1] = read();//倒着
	mergesort(a, 1, n);
	printf("%lld", ct);

	return 0;
}

或者小小改个符号？

#include <iostream>
#include <cstdio>
using namespace std;
int a[500005], arr[500005];
long long ct;
int read(){
	char c = getchar();
	int x = 0;
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}return x;
}void merge(int *a, int left, int mid, int right){
	int i = left, j = mid + 1, ctt = left;
	while(i <= mid && j <= right){
		if(a[i] >= a[j]) arr[ctt++] = a[i++];//改成大于等于
		else{
			arr[ctt++] = a[j++];
			ct += mid - i + 1;
		}
	}while(i <= mid) arr[ctt++] = a[i++];
	while(j <= right) arr[ctt++] = a[j++];
	for(int i = left; i <= right; i++){
		a[i] = arr[i];
	}
}void mergesort(int *a, int left, int right){
	if(left >= right) return;
	int mid = (left + right) / 2;
	mergesort(a, left, mid);
	mergesort(a, mid + 1, right);
	merge(a, left, mid, right);
}
int main(){
	int n = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	mergesort(a, 1, n);
	printf("%lld", ct);

	return 0;
}