一、學習目標

• 理解分治（Divide & Conquer模板與遞迴不變量。
• 掌握 QuickSort（原地、平均快）與 MergeSort（穩定、最壞 O(n log n)）的核心實作細節與適用場合。
• 以分治思維解兩類題：統計型（反轉數 Inversions）與計數型前綴和（Subarray Sums II）。

二、觀念說明

分治與遞迴模板

• 分（Divide）：把問題切成結構相同的子問題；
• 治（Conquer）：遞迴解子問題；
• 合（Combine）：把子結果合回原問題的答案。
• 常見不變量：子區間 [l, r]；base case：l >= r（空或單元素）。

MergeSort（穩定、保證 O(n log n)）

• 流程：切半 → 排左 → 排右 → 線性合併兩段有序序列。
• 穩定：相等元素相對次序不變。
• 空間：需 O(n) 暫存陣列。
• 適用：需要穩定性、要避免最壞 O(n^2)（如幾乎有序資料）。

QuickSort（原地、平均 O(n log n)）

• 流程：選樞紐 pivot → 分區（小於在左，大於在右）→ 遞迴。
• 分區法：Hoare（雙指標、交換少、好實做）或 Lomuto（單指標、易理解）。
• 隨機化樞紐能避免退化；尾遞迴優化可減少棧深。
• 不穩定：相等元素可能換序。
• 適用：在地、常數小、平均非常快。

何時用哪個？

• 要穩定或保證最壞界：MergeSort。
• 在地、平均快且不在意穩定性：QuickSort（隨機樞紐）。

三、CSES實戰演練

題目1 : Inversions — 反轉數（分治 + 合併計數）

題意：
給長度 n 的陣列，計數反轉對 (i < j 且 a[i] > a[j]) 的數量。
解題思路：
MergeSort 的合併階段同時計數跨段反轉數：當 left[i] > right[j]，則 left[i..m] 都大於 right[j]，一次加上 (m - i + 1)。

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

long long merge_and_count(vector<long long>& a, vector<long long>& tmp, int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    long long inv = 0;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            inv += (m - i + 1);
        }
    }
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; ++p) a[p] = tmp[p];
    return inv;
}

long long sort_and_count(vector<long long>& a, vector<long long>& tmp, int l, int r) {
    if (l >= r) return 0;
    int m = (l + r) >> 1;
    long long inv = 0;
    inv += sort_and_count(a, tmp, l, m);
    inv += sort_and_count(a, tmp, m + 1, r);
    inv += merge_and_count(a, tmp, l, m, r);
    return inv;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    cin >> n;
    vector<long long> a(n), tmp(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    long long ans = sort_and_count(a, tmp, 0, n - 1);
    cout << ans << "\n";
    return 0;
}

題目2 : Subarray Sums II

原題:
https://cses.fi/problemset/task/1661

題意：
長度 n 的整數陣列（可有負數），計算子陣列和等於 x 的個數。

解題思路：
前綴和 pref[j]，想要 pref[j] - pref[i-1] = x，等價 pref[i-1] = pref[j] - x。
遍歷 pref[j]，用 unordered_map<long long, long long> 存出現次數並累加答案。注意初始化 cnt[0] = 1（空前綴）。

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

int main() {
    int n; long long x;
    cin >> n >> x;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    unordered_map<long long, long long> cnt;

    cnt[0] = 1; // 空前綴
    long long ans = 0, pref = 0;
    for (int i = 0; i < n; ++i) {
        pref += a[i];
        long long need = pref - x;
        auto it = cnt.find(need);
        if (it != cnt.end()) ans += it->second;
        ++cnt[pref];
    }
    cout << ans << "\n";
    return 0;
}

四、Leetcode實戰演練

題目1 : Sort Colors

原題:
https://leetcode.com/problems/sort-colors/description/

題意：
陣列只含 0/1/2，請原地排序成 0...0 1...1 2...2。

解題思路：三指標 l, i, r：
nums[i]==0 → 與 nums[l] 交換，l++, i++
nums[i]==2 → 與 nums[r] 交換，r--（i 不動）
nums[i]==1 → i++

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0, i = 0, r = (int)nums.size() - 1;
        while (i <= r) {
            if (nums[i] == 0) {
                swap(nums[i++], nums[l++]);
            } else if (nums[i] == 2) {
                swap(nums[i], nums[r--]); // i 不前進
            } else {
                i++;
            }
        }
    }
};

題目2 : Sort an Array

原題:
https://leetcode.com/problems/sort-an-array/description/

題意：
實作排序並回傳有序陣列。

思路：
用 MergeSort；需要 O(n) 暫存，但穩定且最壞仍 O(n log n)。

class Solution {
    void mergeVec(vector<int>& a, vector<int>& tmp, int l, int m, int r) {
        int i = l, j = m + 1, k = l;
        while (i <= m && j <= r) {
            if (a[i] <= a[j]) tmp[k++] = a[i++];
            else tmp[k++] = a[j++];
        }
        while (i <= m) tmp[k++] = a[i++];
        while (j <= r) tmp[k++] = a[j++];
        for (int p = l; p <= r; ++p) a[p] = tmp[p];
    }

    void mergesort(vector<int>& a, vector<int>& tmp, int l, int r) {
        if (l >= r) return;
        int m = (l + r) >> 1;
        mergesort(a, tmp, l, m);
        mergesort(a, tmp, m + 1, r);
        mergeVec(a, tmp, l, m, r);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> tmp(nums.size());
        mergesort(nums, tmp, 0, (int)nums.size() - 1);
        return nums;
    }
};