POJ 2299 Ultra-QuickSort：線段樹 + 離散化求逆序數

POJ 2299 Ultra-QuickSort：線段樹 + 離散化求逆序數

題目重述

給定長度 n < 500,000 的排列（元素 0~999,999,999），求將其排序所需的最少相鄰交換次數，即逆序數。

核心思路：離散化 + 線段樹單點更新區間查詢

1. 離散化：將原數組複製、排序、去重，映射到 1..m（m ≤ n），保持相對大小關係。
2. 線段樹維護前綴計數：從左到右掃描，對當前值 rank，查詢 (rank+1, m] 區間和（即已出現且大於當前值的個數），累加到答案；然後在 rank 處 +1。

代碼實現（C++）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 500005;
LL sum[MAXN<<2], a[MAXN], h[MAXN];

void update(int rt, int l, int r, int p, LL v) {
    if (l == r) { sum[rt] += v; return; }
    int mid = (l+r)>>1;
    if (p <= mid) update(rt<<1, l, mid, p, v);
    else update(rt<<1|1, mid+1, r, p, v);
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
LL query(int rt, int l, int r, int L, int R) {
    if (L > r || R < l) return 0;
    if (L <= l && r <= R) return sum[rt];
    int mid = (l+r)>>1;
    return query(rt<<1, l, mid, L, R) + query(rt<<1|1, mid+1, r, L, R);
}

int main() {
    int n;
    while (~scanf("%d", &n) && n) {
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; ++i) {
            scanf("%lld", &a[i]);
            h[i] = a[i];
        }
        sort(h, h+n);
        int m = unique(h, h+n) - h;
        LL ans = 0;
        for (int i = 0; i < n; ++i) {
            int r = lower_bound(h, h+m, a[i]) - h + 1;
            ans += query(1, 1, m, r+1, m);
            update(1, 1, m, r, 1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

複雜度與優化

• 時間 O(n log n)，空間 O(n)。
• 亦可用 BIT (Fenwick Tree) 代替線段樹，代碼更短、常數更小。
• 答案需 long long（n=500k 時最大逆序數 ≈ 1.25e11）。

本題是「離散化 + BIT/線段樹求逆序數」的標準模板題，掌握後可解決所有靜態逆序數統計問題。