求逆序对

查了好久没正确 神奇的求逆序对

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
LL cnt = 0;//逆序数计数

void Merge(int* ar, int l, int mid, int r, int* tmp) {
	int i = l, j = mid + 1;
	int k = 0;

	while (i <= mid && j <= r) {
		if (ar[i] < ar[j]) {
			tmp[k++] = ar[i++];
		}
		else {
			tmp[k++] = ar[j++];
			cnt += mid - i + 1;//比归并排序多的一步
		}
	}
	while (i <= mid)
		tmp[k++] = ar[i++];
	while (j <= mid)
		tmp[k++] = ar[i++];
	for (int i = 0; i < k; ++i)
		ar[l + i] = tmp[i];
}

void solve(int* ar, int l, int r, int* tmp) {
	if (l < r) {
		int mid = l + (r - l) / 2;
		solve(ar, l, mid, tmp);
		solve(ar, mid + 1, r, tmp);
		Merge(ar, l, mid, r, tmp);
	}
}

int main() {
	int n = 0;
	cin >> n;

	int* ar = new int[n];
	int* tmp = new int[n];

	for (int i = 0; i < n; ++i)
		cin >> ar[i];

	solve(ar, 0, n - 1, tmp);

	cout << cnt;

	delete[] ar;
	delete[] tmp;
	return 0;
}