[算法] doj 1067 归并法求逆序对 Ultra-QuickSort

#include <iostream>
#include <cstdio>
using namespace std;
#define mid(x,y) ((x&y) + ((x^y)>>1))
const int N = 500005;long long a[N];
long long ans; // 记录逆序对个数
void merge_sort(int l, int r) {if(l >= r) return;int m = mid(l,r);merge_sort(l, m);merge_sort(m+1, r);long long *arr = new long long[r-l+1];int i = l, j = m+1, k = 0;while(i <= m && j <= r) {if(a[i] <= a[j]) {arr[k++] = a[i++];}else {ans += (m - i + 1);arr[k++] = a[j++];}}while(i <= m) arr[k++] = a[i++];while(j <= r) arr[k++] = a[j++];for(int i = l; i <= r; i++) {a[i] = arr[i-l];}delete []arr;
}
int main() {int n;while(cin >> n, n) {for(int i = 0; i < n; i++) {cin >> a[i];}ans = 0;merge_sort(0, n-1);cout << ans << endl;}return 0;
}