經典算法：數組逆序對計數——歸並排序 O(n log n) 解法

問題定義

數組中 i < j 且 a[i] > a[j] 稱為一個逆序對。求總逆序對數。歸並排序過程中自然統計跨段逆序對。

歸並統計原理

合併兩個有序子數組 [L...M] 和 [M+1...R] 時：

• 若 left[p] > right[q]，則 left[p] 及其後所有元素均與 right[q] 構成逆序對
• 計數增加 q - (M+1) + 1 = q - M

完整 C++ 實現

class Solution {
public:
    int InversePairs(vector& data) {
        return mergeSort(data, 0, data.size()-1);
    }
    int mergeSort(vector& a, int l, int r) {
        if (l >= r) return 0;
        int mid = (l+r)/2;
        int cnt = mergeSort(a, l, mid) + mergeSort(a, mid+1, r);
        vector tmp(r-l+1);
        int i=l, j=mid+1, k=0;
        while (i<=mid && j<=r) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else { tmp[k++] = a[j++]; cnt += mid - i + 1; }
        }
        while (i<=mid) tmp[k++] = a[i++];
        while (j<=r) tmp[k++] = a[j++];
        copy(tmp.begin(), tmp.end(), a.begin()+l);
        return cnt;
    }
};

關鍵細節

1. 臨時數組 tmp 避免重複分配
2. 合併後 必須回寫原數組，保證上層有序性
3. 長整型防溢出（n=10⁵ 時最大 ~5×10⁹）

複雜度

時間 O(n log n)，空間 O(n)（臨時數組）。優於樹狀數組/線段樹的常數因子。

擴展應用

同樣思想可解：區間逆序對查詢（莫隊/主席樹）、逆序對構造、最小交換次數排序等。