POJ 2299 Ultra-QuickSort 逆序對計數：樹狀數組 + 離散化

求數組逆序對數量的經典問題。n ≤ 500,000，O(n²) 暴力不可行，需 O(n log n) 算法。本文講解樹狀數組（Fenwick Tree）配合離散化的解法。

問題轉化

逆序對定義：i < j 且 a[i] > a[j]。遍歷數組，對於每個 a[i]，查詢「已處理元素中大於 a[i] 的個數」即為以 i 為右端點的逆序對數。累加即得答案。

離散化：將值域映射到 [1..n]

樹狀數組下標需為連續正整數。原數組值可能很大、稀疏、含負數。離散化步驟：

1. 複製數組並排序去重
2. 每個原值二分查找其在有序唯一值數組中的排名（1-based）
3. 排名保持原值的相對大小關係，逆序對數量不變

例：[9, 1, 0, 5, 4] → 排序去重 [0,1,4,5,9] → 映射 [5, 2, 1, 4, 3]

樹狀數組操作

• update(pos, 1)：在位置 pos 加 1，表示出現了一個值
• query(pos)：查詢前綴和 [1..pos]，即「≤ 當前值的已處理元素個數」
• 當前元素排名 r，已處理總數 i-1，則大於它的個數 = (i-1) - query(r)

完整代碼 (C++)

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

struct BIT {
    int n; vector t;
    BIT(int n=0): n(n), t(n+1, 0) {}
    void add(int x, int v=1) { for(; x<=n; x+=x&-x) t[x] += v; }
    int sum(int x) { int r=0; for(; x>0; x-=x&-x) r+=t[x]; return r; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n && n) {
        vector a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        // 離散化
        vector vals = a;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        for (int& x : a) x = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        // 統計逆序對
        BIT bit(vals.size());
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += i - bit.sum(a[i]);  // i = 已處理個數
            bit.add(a[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n log n)（排序 + n 次 BIT 操作）
• 空間：O(n)

對比：歸並排序法

歸並排序過程中合併步驟天然統計逆序對，代碼更短、常數更小，但 BIT 靈活性更強（可支持區間查詢、修改等動態操作）。面試/競賽中兩者皆可，掌握 BIT 更具通用性。

關鍵點總結

1. 離散化只改變值的表示，不改變相對大小順序
2. BIT 下標從 1 開始，離散化映射到 [1..m]
3. 逆序對計數公式：ans += processed_count - query(rank)
4. 答案可能達 n*(n-1)/2 ≈ 1.25e11，必須用 64 位整型（long long/int64_t）

此題是「離散化 + 樹狀數組」的標準模板題，同技巧廣泛應用於區間第 K 小、動態逆序對、矩形面積並等問題。