叛逆的隊伍

patricklai7528 LV 1 SU @ 2025-5-30 8:12:51

📘 叛逆的隊伍

🧠 知識點解析

這是一道經典的逆序對統計（Inversion Count）問題，目的是找出陣列中有多少對 $(i, j)$ 滿足：

$1 \leq i < j \leq n$
$a_i > a_j$

這樣的問題可以通過以下幾種方法解決：

暴力解法：雙重迴圈，時間複雜度 $O(n^2)$ ，無法通過大資料量。
歸併排序：改寫 merge sort，統計在 merge 階段遇到的逆序對，時間複雜度為 $O(n \log n)$ 。
樹狀陣列或線段樹：將數字離散化後，從後往前統計小於當前值的數量，並將當前值加入統計。
平衡二元搜尋樹（如AVL樹）：每次插入時統計左子樹大小，可即時得知小於目前值的數量。

本題程式碼使用的是第 4 種方法：AVL 樹動態維護大小與插入過程統計逆序對。

🔍 逐行程式碼解析

#include <iostream>
#include <algorithm>
using namespace std;

👉 引入標準輸入輸出與算法庫。

struct Node {
    int val, height, size, count;
    Node *left, *right;
    Node(int v) : val(v), height(1), size(1), count(1), left(nullptr), right(nullptr) {}
};

👉 定義 AVL 樹節點結構：

val：當前節點的值
height：以此節點為根的高度
size：以此節點為根的子樹節點總數（含重複值）
count：此值在樹中出現的次數
left、right：左右子樹

int height(Node* node) {
    return node ? node->height : 0;
}

👉 安全地取得某節點的高度。

int getSize(Node* node) {
    return node ? node->size : 0;
}

👉 安全地取得某節點子樹大小。

void update(Node* node) {
    if (node) {
        node->height = 1 + max(height(node->left), height(node->right));
        node->size = node->count + getSize(node->left) + getSize(node->right);
    }
}

👉 更新節點的高度與大小。

int balanceFactor(Node* node) {
    return height(node->left) - height(node->right);
}

👉 計算節點平衡因子，用於 AVL 自動旋轉。

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
    x->right = y;
    y->left = T2;
    update(y);
    update(x);
    return x;
}

👉 執行右旋操作，維持 AVL 樹平衡。

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;
    y->left = x;
    x->right = T2;
    update(x);
    update(y);
    return y;
}

👉 執行左旋操作。

Node* insert(Node* node, int val, int& countSmaller) {
    if (!node) return new Node(val);

👉 如果樹是空的，創建新節點。

    if (val == node->val) {
        node->count++;
        countSmaller += getSize(node->left);

👉 插入重複元素：更新 count，並統計左子樹大小。

    } else if (val < node->val) {
        node->left = insert(node->left, val, countSmaller);

👉 小於當前節點值：遞迴左子樹。

    } else {
        countSmaller += getSize(node->left) + node->count;
        node->right = insert(node->right, val, countSmaller);
    }

👉 大於當前值，表示左子樹所有節點與當前節點都比它小，累加統計。

    update(node);

    int balance = balanceFactor(node);

👉 每次插入後都需更新節點與檢查平衡因子。

    if (balance > 1 && val < node->left->val) return rotateRight(node);
    if (balance < -1 && val > node->right->val) return rotateLeft(node);
    if (balance > 1 && val > node->left->val) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (balance < -1 && val < node->right->val) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

👉 根據平衡因子與插入位置進行對應的 AVL 樹旋轉操作。

    return node;
}

👉 返回平衡後的樹根。

int main() {
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];

👉 輸入士兵數與戰鬥力陣列。

    Node* root = nullptr;
    long long inv_count = 0;

👉 初始化 AVL 樹與逆序對計數器。

    for (int i = n - 1; i >= 0; i--) {
        int countSmaller = 0;
        root = insert(root, a[i], countSmaller);
        inv_count += countSmaller;
    }

👉 從右到左插入元素，每次插入都統計當前值右側小於它的個數（即逆序對）。

    cout << inv_count << endl;
    return 0;
}

👉 輸出逆序對總數。

🖼️ 示意圖

以 2 4 1 3 5 為例，我們從後往前：

插入 5 → 沒有比它小的 → 0
插入 3 → 3 < 5 → 1
插入 1 → 1 < 3 & 1 < 5 → 2
插入 4 → 4 > 1, 3 → 插入右子樹，countSmaller = 2
插入 2 → 2 > 1 → 插入右子樹，countSmaller = 1

總共：0 + 1 + 2 + 2 + 1 = 6（錯！原來從右向左的順序搞反了！）

正確應是從左往右，用 insert 統計「右側比它小的數」，所以程式是從後向前掃，建立 BST 過程中，統計的是目前元素右側有多少比它小的元素，這些就是 (i, j) 逆序對。

✅ 完整程式碼

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int val, height, size, count;
    Node *left, *right;
    Node(int v) : val(v), height(1), size(1), count(1), left(nullptr), right(nullptr) {}
};

int height(Node* node) {
    return node ? node->height : 0;
}

int getSize(Node* node) {
    return node ? node->size : 0;
}

void update(Node* node) {
    if (node) {
        node->height = 1 + max(height(node->left), height(node->right));
        node->size = node->count + getSize(node->left) + getSize(node->right);
    }
}

int balanceFactor(Node* node) {
    return height(node->left) - height(node->right);
}

Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;
    x->right = y;
    y->left = T2;
    update(y);
    update(x);
    return x;
}

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;
    y->left = x;
    x->right = T2;
    update(x);
    update(y);
    return y;
}

Node* insert(Node* node, int val, int& countSmaller) {
    if (!node) return new Node(val);
    if (val == node->val) {
        node->count++;
        countSmaller += getSize(node->left);
    } else if (val < node->val) {
        node->left = insert(node->left, val, countSmaller);
    } else {
        countSmaller += getSize(node->left) + node->count;
        node->right = insert(node->right, val, countSmaller);
    }

    update(node);

    int balance = balanceFactor(node);
    if (balance > 1 && val < node->left->val) return rotateRight(node);
    if (balance < -1 && val > node->right->val) return rotateLeft(node);
    if (balance > 1 && val > node->left->val) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (balance < -1 && val < node->right->val) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }

    return node;
}

int main() {
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];

    Node* root = nullptr;
    long long inv_count = 0;

    for (int i = n - 1; i >= 0; i--) {
        int countSmaller = 0;
        root = insert(root, a[i], countSmaller);
        inv_count += countSmaller;
    }

    cout << inv_count << endl;
    return 0;
}

View all 1 solutions

ID: 991
Time: 150ms
Memory: 128MiB
Difficulty: 9
Tags: (None)
# Submissions: 45
Accepted: 2
Uploaded By: patricklai7528

1 solutions