题意：废话了一大堆就是要你去求一个序列冒泡排序所需的交换的次数。
思路：实际上是要你去求一个序列的逆序队数
看案例：
9 1 0 5 4
9后面比它小的的数有4个
1后面有1个
0后面没有
5后面1个
4后面没有
所以结果为4+1+0+1+0=6
所以逆序对的定义假设不清楚能够自己总结了
这道题说白了就是要你用归并排序求逆序对数。
以下是搜到某牛给的逆序对数的方法：
如果回溯到某一步，后面的两部分已经排好序（就是说当前须要归并的两个部分都是分别有序的）。如果这两个序列为
序列a1：2 3 5 9
序列a2：1 4 6 8
此时我们的目的就是要将a1和a2合并为一个序列。
因为在没排序前a2序列一定所有都是在a1序列之后的，当我们比較a2的1与a1的2时，发现1<2依照归并的思想就会先记录下a2的1。而这里实际上就是对冒泡排序的优化，冒泡是将a2的1依次与a1的9,5,3,2交换就需要4次。而归并却仅仅有一次就完毕了。要怎么去记录这个4呢。实际上因为1比2小而2后面还有4个数，也就是说那我的结果就必需要+4，也就是记录a1序列找到第一个比a2某一个大的数。他后面还余下的数的个数就是要交换的次数。
我的AC代码（依照刘汝佳书思路来的，大神别喷 ==）：
#include<stdio.h>
#include<string.h>
int n,a[500005],b[500005];
__int64 sum;
void merge_sort(int x,int y)
{
if(y-x>1)
{
int m=x+(y-x)/2;
int p=x,q=m,i=x;
merge_sort(x,m);
merge_sort(m,y);
while(p<m||q<y)
{
if(q>=y||(p<m&&a[p]<=a[q]))
b[i++]=a[p++];
else
{
sum+=m-p;
b[i++]=a[q++];
}
}
for(i=x;i<y;i++)a[i]=b[i];
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0)break;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sum=0;
merge_sort(0,n);
printf("%I64d\n",sum);
}
return 0;
}