【题目描述】

有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000)，若i<j，并且A[i]>A[j]，则称A[i]与A[j]构成了一个逆序对，求数列A中逆序对的个数。

例如，5 2 4 6 2 3 2 6，可以组成的逆序对有

（5 2），（5 4），（5 2），（5 3），（5 2），

（4 2），（4 3），（4 2），

（6 2），（6 3），（6 2），

（3 2）

共：12个

【输入描述】

共两行，第一行有一个正整数n，第二行有n个整数。

【输出描述】

只有一行为逆序对个数。

【样例输入】

8
5 2 4 6 2 3 2 6

【样例输出】

12

所谓逆序对的问题，即对给定的数组序列，求其逆序对的数量。

从逆序对定义上分析，逆序对就是数列中任意两个数满足大的在前，小的在后的组合。如果将这些逆序对都调整成顺序（小的在前，大的在后），那么整个数列就变得有序，即排序。因而，容易想到冒泡排序的机制正好是利用消除逆序来实现排序的，也就是说，交换相邻两个逆序数，最终实现整个序列有序，那么交换的次数即为逆序对的数量。

当然，这个题目，用的是合并操作来分析。

在合并操作中，我们假设左右两个区间元素为：

左边：{3 4 7 9}     右边 {1 5 8 10}

那么，合并的第一步就是比较3和1，然后将1取出来，放到辅助数组中，这个时候我们发现，右边的区间如果是当前比较的较小值，那么其会于左边剩余的数字产生逆序关系，也就是说1和3、4、7、9都产生了逆序关系，我们可以一下子统计出4对逆序对。

接下来3，4取下来放到辅助数组后，5与左边剩下的7、9产生了逆序关系，我们可以统计出2对。

以此类推，8与9产生1对，那么总共有4+2+1对。这样统计的效率就会大大提高，便可较好地解决逆序对问题。                                                  

void msort(int s, int t){
	if(s==t) return ;  //如果只有一个数字则返回，无须排序
	int mid=(s+t)/2; 
	msort(s,mid);    //分解左序列
	msort(mid+1,t);  //分解右序列 
	int i=s, j=mid+1, k=s;  //接下来合并
	
	while(i<=mid && j<=t){
	
		if(a[i]<=a[j]){
			r[k]=a[i];
			k++;
			i++;
		}else{
			r[k]=a[j];
			k++;
			j++;
			ans+=mid-i+1; //统计产生逆序对的数量 
		}
	}
	while(i<=mid){  //复制 左边子序列剩余 
		r[k]=a[i];
		k++;
		i++;
	}
	while(i<=mid){  //复制 右边子序列剩余 
		r[k]=a[j];
		k++;
		j++;
	}
	for(int i=s;i<=t;i++)
		a[i]=r[i]; 
}

其中，ans+=mid-i+1; 这句代码统计新增逆序对的数量，ans作为全局变量，用于统计逆序对的数量，此时ans要增加左边区间剩余元素的个数。当归并排序结束后，逆序对问题也得到解决，ans即为逆序对的数量。