题目来源：Ultra-QuickSort
题意
现在随机给你一组数，每次可以交换相邻的两个数，问最少交换几次可以使得这组数变为升序
分析
显然如果两个相邻的数如果是逆序则需要需要交换这两个数字。现在考虑两个不相邻的逆序对a[i] 和 a[j](a[i] > a[j], i < j)，对于这两个中间的数a[k]如果a[k] > a[j]，则需要交换a[k]和a[j] 而且交换后不会影响a[i] 和 a[k]的顺序关系；如果a[k] < a[j]，a[k] > a[i] 则不用考虑a[k]了，需要考察别的数。最终可以发现所有逆序的数字都需要直接或间接的进行交换。间接是指他们两者不相邻，需要借助别的数字来交换位置使得他俩相邻，然后才能相互交换。问题就转化为了求一个数列中有多少个逆序对。逆序对的个数即为答案。
由于数的范围非常大，用树状数组求逆序对的时候需要进行离散化。当然用归并排序也可以。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 5000010;
int n;
long long a[N];
int b[N];
long long tree[N];
int lb(int x) { return x & (~x + 1); }
long long sum(int x)
{
long long tot = 0;
for (int i = x; i; i -= lb(i))
tot += tree[i];
return tot;
}
void add(long long num, int x)
{
for (int i = x; i <= n; i += lb(i))
tree[i] += num;
}
const bool cmp(const int i, const int j)
{
return i == j ? (i < j) : (a[i] < a[j]);
}
int main()
{
while (~scanf("%d", &n) && n)
{
memset(tree, 0, sizeof(tree));
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
scanf("%lld", a + i);
b[i] = i;
}
std::sort(b + 1, b + 1 + n, cmp);
for (int i = n; i; --i)
{
ans += sum(b[i]-1);
add(1ll, b[i]);
}
printf("%lld\n", ans);
}
return 0;
}
