蒟蒻写文，难免出错，欢迎大佬来踩！

逆序对的定义

---

 

 

其实逆序对是一个非常简单的概念。对于一个数组中的任何一个数，只要有一个在它后面的数小于它本身，那么这两个数字就构成了一个逆序对。我们举一个例子。

对于这样一个数组

A[4]={1,4,2,3};

 其中有两对逆序对，分别是（4，2）和（4，3）。

 

求逆序对个数的方式

---

 

 

有没有感觉刚才找逆序对的方法与归并排序很相似。没错，我们就使用归并排序的方法统计逆序对个数。

首先，我们要先执行分组的操作，对于数组A[0..n]，我们通过归并的方式分组，最终我们能将数组成对分成n+1个小组，每组一个数据。

紧接着，我们开始两组两组地合并。但是在和并一定要注意记录，当出现前一组的待和并数据突然小于后一组待和并数据时，表明发现了逆序对。至于发现了多少个逆序对呢？应该是左侧一组的剩余数据数，这是因为我们在合并的时候左右两组已经是有序的序列了。经过统计，我们会在归并排序和并过程完成后得到逆序对个数。

那么实现上述思路的C++代码如下：

/*import guideint a[] shold be set as the target arrayint aux[] shoule be set as the auxilary arrayALWAYS call he function distribute()DO NOT call the function _combine()  for it is not complete. */void _combine(int left,int mid,int right){	int l=left,r=mid+1,aux_ptr=left;	while(l<=mid&&r<=right){		if(a[l]>a[r]){			aux[aux_ptr++]=a[r++];			ans+=mid-l+1;		}else aux[aux_ptr++]=a[l++];	}	while(l<=mid) aux[aux_ptr++]=a[l++];	while(r<=right) aux[aux_ptr++]=a[r++];	for(int i=left;i<=right;i++) a[i]=aux[i];	return;}void distribute(int left,int right){	if(left>=right) return;	else{		int mid=(left+right)>>1;		distribute(left,mid);		distribute(mid+1,right);		combine(left,mid,right);		return;	}}