逆序对 题解

题目

有关必回

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int a[N], b[N];
int n, ans;
void Sort(int l, int r) {
	if (l == r) return ;
	int mid = (l + r) / 2;
	Sort(l, mid);
	Sort(mid + 1, r);
	int i = l, j = mid + 1, k = l;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j]) {
			b[k] = a[i];
			k++;
			i++;
		} else {
			b[k] = a[j];
			k++;
			j++;
			ans += mid - i + 1;
		}
	}
	while (i <= mid) {
		b[k] = a[i];
		k++;
		i++;
	}
	while (j <= r) {
		b[k] = a[j];
		k++;
		j++;
	}
	for (int i = l; i <= r; i++) {
		a[i] = b[i];
	}
}
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	Sort(1, n);
	cout << ans;
	return 0;
}