反序數量 (APCS 2018-06 高級) 的題解

前置知識

這題是「合併排序順便數反序對」的經典題，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

  • 分治與合併排序：NTUCPC Guide〈分治法〉——它的例題「逆序數對」正是本題；語法書 11.12 的合併排序法是這題的骨架；吳邦一《AP325》第 5 章的 P-5-4 也是本題（教材 PDF 第 150～154 頁；Python 版第 5 章），先講 \(O(n \log^2 n)\) 再改成 \(O(n \log n)\)。

簡潔題意

數列 \(a_1, \ldots, a_n\)，數「前面的比後面的大」的位置對 \((i, j)\)（\(i < j\) 且 \(a_i > a_j\)）有幾對；數值相同、位置不同的要分開算（\(n \le 10^5\)、\(0 \le a_i \le 10^6\)；APCS 逐筆給分）。

先拿下小測資：每一對都看

兩層迴圈枚舉所有 \(i < j\)，\(a_i > a_j\) 就加一。\(n = 10^5\) 時是 \(5 \times 10^9\) 對，本站實測一筆要 \(1.7 \sim 12\) 秒、大多超過 \(2\) 秒的時限，分數靠不住——但小的測資它一定對（本題 \(n \le 2\) 的計分測資有 \(4\) 筆）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    long long count = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)      // n = 10^5 時 5 × 10^9 對，跑不完
            if (a[i] > a[j]) count++;
    cout << count << '\n';
    return 0;
}

從小測資到 100 分：切半、各自數、再數「跨半」的

把數列切成左右兩半。一個反序對的兩個數要嘛都在左半、要嘛都在右半、要嘛一左一右——前兩種就是「同一個問題、小一半」，交給遞迴；只剩跨半的要自己數：左半的某個數 \(x\) 和右半的某個數 \(y\)，\(x > y\) 就是一對。

如果左右兩半各自已經排好序，跨半的就很好數：像合併排序那樣把兩半合併，每次比較兩邊最前面的數，從右半拿出一個數 \(y\) 的那一刻，左半還沒拿出來的每個數都比 \(y\) 大（左半排好序，前面的拿走了、剩下的都不小於目前比較的那個，而它比 \(y\) 大）——所以反序對加上「左半剩下的個數」。從左半拿出來的數不加（它不比右邊任何一個大）。兩半相等時先拿左半，才不會把相等算成反序。

圖 1：範例的左半 [1 3 9] 與右半 [2 8 9] 合併，從右半拿出 2 時左半還剩 2 個、拿出 8 時剩 1 個、拿出 9 時剩 0 個，跨半反序對 3；加上兩半內部的 1 和 2，共 6

合併完這一段就排好序了，正好給上一層用——這就是合併排序，只是多了一行加總。

#include <bits/stdc++.h>
using namespace std;

vector<long long> a, tmp;

// 數 a[l..r-1] 裡的反序對，順便把這一段排好序
long long countAndSort(int l, int r) {
    if (r - l <= 1) return 0;                           // 一個數：沒有反序對
    int mid = (l + r) / 2;
    long long count = countAndSort(l, mid) + countAndSort(mid, r);   // 兩半各自數、各自排好

    int i = l, j = mid, k = l;                          // i 走左半、j 走右半、k 寫到 tmp
    while (i < mid && j < r) {
        if (a[i] <= a[j]) {                             // 相等先拿左：相等不算反序
            tmp[k++] = a[i++];
        } else {
            count += mid - i;                           // 右半的 a[j] 比左半剩下的 mid - i 個都小
            tmp[k++] = a[j++];
        }
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int t = l; t < r; t++) a[t] = tmp[t];          // 排好的寫回去
    return count;
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    tmp.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << countAndSort(0, n) << '\n';
    return 0;
}

每一層合併總共掃 \(n\) 個數、切半只能切 \(\log_2 n \approx 17\) 層，\(O(n \log n)\)。答案要 long long：\(n = 10^5\) 嚴格遞減時有 \(\dfrac{n(n-1)}{2} \approx 5 \times 10^9\) 對。

另一種做法：從左到右數「前面有幾個比我大」

對每個位置 \(j\)，反序對的數量＝前面比 \(a_j\) 大的數有幾個。數值只有 \(0 \sim 10^6\)，用一個「每個數值出現幾次」的計數陣列，一邊往右走一邊登記；「前面比我大的有幾個」就是「前面總數減去前面不大於我的個數」，而「不大於我的個數」是計數陣列的前綴和——每走一步前綴和都在變，用 Fenwick 樹（BIT）維護，查詢和更新各 \(O(\log V)\)，總共 \(O(n \log V)\)。這條路要先會 BIT，APCS 的範圍用不到，合併排序那條就夠了。

測過再交：範例只有一對相等的數

範例 \(3\ 1\ 9\ 8\ 9\ 2\) 剛好有一對相等的 \(9\)。沒蓋到的：全部相等（答案 \(0\)）、嚴格遞減（答案最大）、已經排好序、只有一個數。

輸入 正確輸出 這一筆在測什麼
1 ／ 5 0 只有一個數（小測資版就能驗）
4 ／ 7 7 7 7 0 全部相等：相等不算反序，合併時「相等先拿左」就是為了這個
5 ／ 5 4 3 2 1 10 嚴格遞減：每一對都是反序，\(\dfrac{5 \times 4}{2}\)
5 ／ 1 2 3 4 5 0 已排好序
用程式造：\(n = 10^5\)、\(a_i = n - i\) 4999950000 答案超過 int（小測資版跑不完，用合併版驗）

五筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 相等也算反序（合併時 a[i] < a[j] 才拿左）：範例印 7（多算了那對 \(9\)）。
  • 答案用 int：範例和小測資都過，嚴格遞減的大測資溢位。
  • 合併後沒把排好的寫回原陣列：上一層拿到的兩半沒排序，「左半剩下的都比 \(y\) 大」不成立——範例印 3。
  • 兩層迴圈硬上 \(n = 10^5\)：\(5 \times 10^9\) 次比較，本站實測最慢的測資要 \(12\) 秒，TLE。
  • 遞迴邊界寫成 r - l == 0：長度 \(1\) 的段切成 \(0\) 和 \(1\)，無窮遞迴。