题解

做不对的一定没读透CSP一本通（
众所周知，冒泡排序每交换一次就会减少一对逆序对
而最后会达成升序，即逆序对数量为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;
}

时间复杂度：$O(nlog_2n)$