题目链接：uva 10810 - Ultra-QuickSort
题目大意：给出一个序列，每次交换两个数，这两个数之间的距离就是代价，问说要将序列排序的总代价是多少。
解题思路:归并排序下的逆序数的个数。
#include <stdio.h>
#include <string.h>
const int N = 500005;
typedef long long ll;
int n, g[N], f[N];
ll Msort(int l, int r, int* a, int* b) {
if (r - l == 1) return 0;
int m = (l + r) / 2;
ll ans = Msort(l, m, a, b) + Msort(m, r, a, b);
int p = l, q = m, c = l;
while (p < m || q < r) {
if (q >= r || (p < m && a[p] <= a[q])) b[c++] = a[p++];
else {
ans += m - p;
b[c++] = a[q++];
}
}
for (int i = l; i < r; i++) a[i] = b[i];
return ans;
}
int main() {
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++) scanf("%d", &g[i]);
printf("%lld\n", Msort(0, n, g, f));
}
return 0;
}