HDU 3743 Frosh Week：離散化與樹狀數組求逆序數完整解析

問題背景與核心任務

在 HDU 3743 Frosh Week 這道經典題目中，我們面對的是一個看似簡單但極具代表性的算法問題：給定一個長度不超過一百萬的學生編號序列，僅允許交換相鄰學生，求將序列按編號升序排列所需的最小交換次數。這本質上就是求序列的逆序數——即滿足 i < j 且 a[i] > a[j] 的數對個數。

為什麼需要離散化？

學生編號的範圍可能非常大（如 32 位整數），但數量最多一百萬。若直接用編號作為樹狀數組的下標，空間會爆炸。離散化的核心思想是：將原始數值映射為 1..n 的連續排名，保持相對大小關係不變。具體步驟：

1. 讀入所有編號，記錄其原始位置 id
2. 按編號升序排序
3. 依次賦予新值：第一個為 1，之後若與前一個不同則遞增，否則沿用前一個值
4. 再按原始 id 排序回原順序，完成離散化

樹狀數組（Fenwick Tree）高效統計逆序數

離散化後，數值範圍縮減至 [1, n]，即可使用樹狀數組。遍歷序列時，對於當前值 x：

• sum(n) - sum(x) 即為已出現且大於 x 的元素個數，累加到答案
• 隨後 update(x, 1) 將 x 加入統計

時間複雜度 O(n log n)，空間 O(n)，完美應對百萬規模。

關鍵代碼實現（C++）

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

const int MAXN = 1000005;
int n, bit[MAXN];

struct Node {
    int val, id;
} a[MAXN];

bool cmpVal(const Node &x, const Node &y) { return x.val < y.val; }
bool cmpId(const Node &x, const Node &y) { return x.id < y.id; }

int lowbit(int x) { return x & (-x); }

void update(int i, int v) {
    for (; i <= n; i += lowbit(i)) bit[i] += v;
}

int query(int i) {
    int s = 0;
    for (; i > 0; i -= lowbit(i)) s += bit[i];
    return s;
}

int main() {
    while (scanf("%d", &n) != EOF) {
        memset(bit, 0, sizeof(bit));
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i].val);
            a[i].id = i;
        }
        // 離散化
        sort(a + 1, a + n + 1, cmpVal);
        a[1].val = 1;
        for (int i = 2; i <= n; ++i)
            a[i].val = (a[i].val != a[i-1].val) ? i : a[i-1].val;
        sort(a + 1, a + n + 1, cmpId);
        // 統計逆序數
        long long ans = 0;
        for (int i = 1; i <= n; ++i) {
            update(a[i].val, 1);
            ans += query(n) - query(a[i].val);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

易錯點提醒

• 答案必須用 64 位整數（long long），逆序數最大可達 n*(n-1)/2 ≈ 5e11
• 離散化時相同值必須映射到相同排名，否則會破壞相對順序
• 輸入可能包含多組測試數據，需 while(scanf(...) != EOF) 循環讀取

總結

本題是離散化 + 樹狀數組求逆序數的教科書級範例。掌握這套「值域壓縮 + 前綴和統計」的組合拳，即可輕鬆解決大數值範圍下的順序統計問題，是競技編程與工程實踐中極高頻的核心技能。