查了好久没正确 神奇的求逆序对
#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;
}