HDU 1394 Minimum Inversion Number：樹狀數組求循環移位最小逆序數

問題描述

給定 0..n-1 的一個排列（n ≤ 5000）。可將前 m 個元素移至末尾（m=0..n-1），共 n 種循環移位。求這 n 個序列中的最小逆序數。

樹狀數組求初始逆序數

標準 BIT：從左到右遍歷，ans += query(n) - query(a[i])，然後 add(a[i], 1)。數值範圍 0..n-1，BIT 下標 +1 避免 0。

循環移位逆序數遞推

設當前序列首元素為 x（值域 0..n-1）。移至末尾後：

• 失去 x 與其後較小元素構成的逆序對：x 個（因排列含 0..x-1）。
• 新增 x 與其後較大元素構成的逆序對：n-1-x 個。
• 變化量：Δ = (n-1-x) - x = n - 1 - 2x。

遞推 inv_{k+1} = inv_k + n - 1 - 2*a[k]（a[k] 為原序列第 k 個元素，0-index）。

參考代碼 (C++)

#include 
using namespace std;
const int MAXN = 5005;
int bit[MAXN], a[MAXN];
int n;
void add(int x, int v) { for (; x <= n; x += x&-x) bit[x] += v; }
int sum(int x) { int r=0; for(; x>0; x-=x&-x) r+=bit[x]; return r; }
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-indexed for BIT
        }
        memset(bit, 0, sizeof(bit));
        long long inv = 0;
        for (int i = 1; i <= n; ++i) {
            inv += sum(n) - sum(a[i]);
            add(a[i], 1);
        }
        long long ans = inv;
        for (int i = 1; i <= n; ++i) {
            int x = a[i] - 1; // original value
            inv += (n - 1 - 2 * x);
            ans = min(ans, inv);
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

BIT 建樹 O(n log n)，遞推 O(n)。總 O(n log n)，n=5000 極快。

關鍵洞察

• 排列性質：值即排名，x 前有 x 個較小數，後有 n-1-x 個較大數。
• 循環移位只改變首尾關係，內部相對序不變，逆序數增減可直接計算。
• 遞推公式 Δ = n - 1 - 2x 推導簡潔，無需重新計算。

總結

• 經典逆序數 + 循環移位技巧題。
• BIT 模板必須熟練（add/sum）。
• 遞推思路：利用問題結構將 O(n²) 降為 O(n)。