题目链接：http://poj.org/problem?id=1804
思路分析：序列的逆序数即为交换次数，所以求出该序列的逆序数即可。
根据分治法思想，序列分为两个大小相等的两部分，分别求子序列的逆序数；对于右子序列中的每一个数，求出左序列中大于它的数的数目，计算的和即为解。
另外，使用Merge排序时，可以很容易求得对于右子序列中的每一个数，左序列中大于它的数的数目。
代码如下：
#include <stdio.h>
#include <limits.h> long long Count = ;
const int MAX_N = + ;
long long A[MAX_N], L[MAX_N], R[MAX_N]; void Merge(long long A[], int p, int q, int r)
{
int i, j, k; int n1 = q - p + ;
int n2 = r - q; for (int i = ; i < n1; ++i)
L[i] = A[p + i];
for (int j = ; j < n2; ++j)
R[j] = A[q + j + ]; i = j = ;
k = p;
L[n1] = INT_MAX;
R[n2] = INT_MAX; while (k <= r)
{
if (L[i] > R[j])
{
A[k++] = R[j++];
Count += n1 - i;
}
else
A[k++] = L[i++];
}
} void Merge_Sort(long long A[], int p, int q)
{
int r = (p + q) / ; if (p < q)
{
Merge_Sort(A, p, r);
Merge_Sort(A, r + , q);
Merge(A, p, r, q);
}
} int main()
{
int n;
int Scenario = ; scanf("%d", &n);
for (int i = ; i < n; ++i)
{
int Num; scanf("%d", &Num); Count = ;
Scenario++;
for (int i = ; i < Num; ++i)
scanf("%lld ", &A[i]); Merge_Sort(A, , Num - );
printf("Scenario #%d:\n%lld\n\n", Scenario, Count);
} return ;
}