題目大意

給定一個 0~n-1 的排列，定義逆序數為 i < j 且 a[i] > a[j] 的數對個數。現可將序列循環左移任意次（首元素移至尾部），求所有循環移位中逆序數的最小值。n ≤ 5000，測試組數多，需 O(n log n) 算法。

核心洞察

1. 靜態逆序數：原序列逆序數可用樹狀數組 O(n log n) 求解。
2. 循環左移效應：將首元素 x 移至尾部，逆序數變化量為 (n-1 - 2*x)。推導：x 原本與後面 n-1 個元素構成數對，其中 x 個比它小（不構成逆序），n-1-x 個比它大（構成逆序）。移至尾部後，它與所有元素構成數對，比它小的 x 個變成逆序，比它大的 n-1-x 個不再是逆序。增量 = x - (n-1-x) = 2x - n + 1，即減少 n-1-2x。
3. 遞推公式：inv[k+1] = inv[k] + n - 1 - 2*a[k]，其中 a[k] 為第 k 次移動前的首元素（原序列第 k 個元素）。

樹狀數組核心原理

樹狀數組利用 lowbit(x) = x & (-x) 將陣列索引映射為樹結構，支援：

• 單點更新：add(i, val) 向上更新所有包含 i 的區間節點。
• 前綴查詢：sum(i) 向下累加所有覆蓋 [1,i] 的區間節點。

圖解關鍵跳躍：

索引:  1  2  3  4  5  6  7  8
lowbit:1  2  1  4  1  2  1  8
樹節點覆蓋範圍:
c[1]=[1,1]  c[2]=[1,2]  c[3]=[3,3]  c[4]=[1,4]
c[5]=[5,5]  c[6]=[5,6]  c[7]=[7,7]  c[8]=[1,8]

完整 AC 代碼

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

const int MAXN = 5005;
int n;
int a[MAXN];      // 原序列 (1-indexed, 值域 1~n)
int c[MAXN];      // 樹狀數組

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

void add(int i, int val) {
    while (i <= n) {
        c[i] += val;
        i += lowbit(i);
    }
}

int sum(int i) {
    int res = 0;
    while (i > 0) {
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            a[i]++; // 值域轉為 1~n，適配樹狀數組
        }
        
        fill(c, c + n + 1, 0);
        long long inv = 0;
        // 計算初始逆序數
        for (int i = 1; i <= n; ++i) {
            add(a[i], 1);
            inv += i - sum(a[i]); // 前 i-1 個元素中 > a[i] 的個數
        }
        
        long long ans = inv;
        // 枚舉循環左移
        for (int i = 1; i < n; ++i) {
            inv += n - 1 - 2 * (a[i] - 1); // a[i] 原值域 0~n-1，此處已 +1
            ans = min(ans, inv);
        }
        cout << ans << '\n';
    }
    return 0;
}

關鍵細節解析

複雜度分析

• 時間：O(n log n) 建樹 + O(n) 遞推 = O(n log n) 每測試組。
• 空間：O(n) 樹狀數組 + O(n) 序列存儲。

樹狀數組 vs 線段樹 對比

擴展應用

• 區間查詢：query(l, r) = sum(r) - sum(l-1)
• 離線區間第 k 小：配合二分答案 + 樹狀數組計數
• 二維樹狀數組：矩陣區間加、點查或點加、區間和
• CDQ 分治：三維偏序、動態逆序數、動態區間第 k 小

總結

HDU 1394 是樹狀數組入門的經典題目。掌握 lowbit 本質、逆序數遞推公式推導、值域映射技巧，即可輕鬆 AC。樹狀數組以代碼簡短、常數極小、功能聚焦著稱，是競程「單點更新+前綴查詢」場景的首選數據結構。