Ultra-QuickSort
题目链接：http://poj.org/problem?id=2299
题目大意：
有一串序列，（其中数字各不相同），每次只能够交换相邻的两个数字，问将其排为升序所需的交换次数。
解题思路：
这道题其实就是求逆序对的数目。可以看下面的博客，讲解了问什么这样的交换次数就是逆序对的数目。（大致就是冒泡排序的思想）
至于求逆序数，如果用朴素的方法，为O（N^2）。不可取。
还有三种 O（NlogN）的方法：
（1） 通过归并排序求逆序对
将一个序列分为左右两端，那么通过遍历两端子序列，可以求出左右两端的逆序对数目。通过分治的方法再将左边和右边分为两端，知道 L=R结束。
归并排序
const int maxn = 555555;
int n, a[maxn], b[maxn];
typedef long long ll;
ll mergesort(int l, int r) {
if (l == r) return 0;
ll cnt = 0;
int m = (l + r) >> 1;
cnt = mergesort(l, m) + mergesort(m + 1, r);
int i = l, j = m + 1, k = l;
while(i <= m && j <= r) {
if (a[i] <= a[j]) b[k++] = a[i++];
else {
b[k++] = a[j++];
cnt += (m - i + 1);
}
}
while(i <= m) b[k++] = a[i++];
while(j <= r) b[k++] = a[j++];
for (i = l; i <= r; i++) a[i] = b[i];
return cnt;
}
int main () {
while(~scanf("%d", &n) && n) {
for (int i = 0; i < n; i++) scanf("%d", a + i);
printf("%I64d\n", mergesort(0, n - 1));
}
return 0;
}
（2）用树状数组求逆序对（必须要离散化，所以比上一种方法略慢）
//树状数组
const int maxn = 555555;
typedef long long ll;
int n;
ll a[maxn], pos[maxn];
struct node {
int v, i;
}e[maxn];
bool cmp(node s, node v){
return s.v < v.v;
}
inline int lowbit(int x) {
return (x & -x);
}
void update(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) a[i] += v;
}
ll query(int x) {
ll ret = 0;
for (int i = x; i; i -= lowbit(i)) ret += a[i];
return ret;
}
int main () {
while(scanf("%d", &n) && n) {
for (int i = 1; i <= n; i++) {
a[i] = 0;
scanf("%d", &e[i].v);
e[i].i = i;
}
//离散化
sort(e + 1, e + n + 1, cmp);
for (int i = 1; i <= n; i++) pos[i] = e[i].i;
int x;
ll ret = 0;
for (int i = 1; i <= n; i++) {
ret += query(pos[i]);
update(pos[i], 1);
}
printf("%I64d\n", (ll)n * (n - 1) / 2 - ret);
}
return 0;
}
（3）用线段树求逆序对（和第二种一样）