早就想學一下歸并排序求逆序對，在這之前只會用樹狀數組來做，有時候還需要離散化，而且效率還不如歸并排序高。
其實還是蠻簡單的，知道歸并排序的原理就很容易知道如何求逆序對了。設數組為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);
}
}