早就想学一下归并排序求逆序对，在这之前只会用树状数组来做，有时候还需要离散化，而且效率还不如归并排序高。
其实还是蛮简单的，知道归并排序的原理就很容易知道如何求逆序对了。设数组为A，关键是在合并的时候，用数组L 和 R 表示左右两个子数组，因为逆序对的个数f(A) = f(L) + f(R) + s(L,R);其中f(L) 和 f(R) 分别表示L 内部 和R内部的逆序对个数，s(L.R)表示大数在L，小数在R的逆序对。因为L和R是已经排好序的，故其实只需求s(L,R).这个可以在合并L和R依次进行比较的时候算出。
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{ //如果L最上面的数大于R的，那么L[i]及后面的数可以和R[j]构成n1-i+1个逆序对
a[k] = R[j++];
count +=(n1 -i + 1); //累加
}
}
归并排序的代码：
void merge(int p,int q,int r){
int n1 = q-p+1,n2 = r-q;
int i,j,k;
for(i = 1;i <= n1; i++)
L[i] = a[p+i-1];
for(j = 1;j <= n2; j++)
R[j] = a[q+j];
L[n1+1] = INF;
R[n2+1] = INF;
i = 1;j = 1;
for(k = p;k <= r;k ++){
if(L[i]<=R[j])
a[k] = L[i++];
else{
a[k] = R[j++];
count +=(n1 -i + 1);
}
}
}
void merge_sort(int p,int r){
if(p<r){
int q = (p+r)/2;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
}
}