逆序數統計：歸並排序分治法 O(n log n) 完整解析

問題定義

給定長度 $n$（$n \le 10^6$）的整數序列，求逆序對數量：$i < j$ 且 $a_i > a_j$ 的對數。答案可能超過 32 位整數，需用 64 位（long long）。

歸並排序分治思想

歸並過程中，將數組分為左右兩半，遞歸排序並統計左右內部逆序對。合併時，若左半元素 $L[i] > R[j]$，則 $L[i..mid]$ 所有元素均大於 $R[j]$（因左右半已有序），一次性新增 $mid - i + 1$ 個逆序對。

算法步驟

1. 分解：遞歸拆分至單元素區間。
2. 解決：單元素區間逆序數為 0。
3. 合併：雙指針合併兩有序子數組，統計跨區間逆序對。

合併過程逆序對計數邏輯

void merge(int l, int mid, int r) {
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
            ans += (long long)(mid - i + 1); // 關鍵：a[i..mid] 都 > a[j]
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    copy(tmp + l, tmp + r + 1, a + l);
}

完整代碼

#include 
using namespace std;
const int MAXN = 1000005;
int a[MAXN], tmp[MAXN];
long long ans;

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    // 合併
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            ans += mid - i + 1;
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int i = l; i <= r; ++i) a[i] = tmp[i];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        ans = 0;
        mergeSort(0, n - 1);
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

• 時間：$O(n \log n)$。每層合併 $O(n)$，共 $\log n$ 層。
• 空間：$O(n)$ 輔助數組 tmp。

遠優於暴力 $O(n^2)$，可處理 $n=10^6$。同樣原理可用於樹狀數組（$O(n \log C)$，$C$ 為值域）或線段樹，但歸並排序最簡潔、常數最小。

關鍵細節與避坑

測試樣例

輸入：
2
2
1 1
3
1 3 2

輸出：
0
1

第二組：(3,2) 唯一逆序對。

延伸應用

• 「小於右側元素個數」（LeetCode 315）：同歸並思路，記錄每個元素右側小於它的個數。
• 「翻轉對」（LeetCode 493）：條件變為 $a_i > 2 a_j$，合併時雙指針預處理。
• 「區間逆序對查詢」：莫隊算法 + 树状数组 / 歸並樹。

總結

歸並排序統計逆序數是「分治 + 有序性利用」的教科書級範例。掌握其合併階段的計數邏輯（mid - i + 1），即可舉一反三解決一系列「有序數組配對計數」問題。代碼簡短、常數極小、無值域限制，是競賽與面試首選方案。