HDU 1394：Minimum Inversion Number（最小逆序數，樹狀數組/線段樹）

一、題目大意

給定一個排列，每次操作將第一個元素移到末尾。求所有循環移位中逆序數的最小值。

二、解題思路

1. 用樹狀數組（BIT）求初始排列的逆序數 ans。
2. 觀察循環移位：將第一個元素 x 移到末尾，逆序數變化量 = (比 x 大的元素個數) - (比 x 小的元素個數)。
即 cur += (n - 1 - cnt) - cnt，其中 cnt 為比 x 小的元素個數（可用 BIT 查詢）。
3. 遍歷所有移位，維護最小值。

三、代碼實現（C++）

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

const int MAXN = 5000 + 10;
int bit[MAXN], a[MAXN];
int n;

int sum(int x) {
    int ans = 0;
    while (x > 0) {
        ans += bit[x];
        x -= x & -x;
    }
    return ans;
}

void add(int x, int d) {
    while (x <= n) {
        bit[x] += d;
        x += x & -x;
    }
}

int main() {
    while (~scanf("%d", &n)) {
        memset(bit, 0, sizeof(bit));
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            a[i]++; // 離散化避免 0 索引
            ans += sum(n) - sum(a[i]); // 統計比 a[i] 大的數
            add(a[i], 1);
        }
        int cur = ans;
        for (int i = 1; i < n; ++i) {
            int cnt = sum(a[i] - 1); // 比 a[i] 小的數
            cur += (n - 1 - cnt) - cnt;
            ans = min(ans, cur);
        }
        printf("%d\n", ans);
    }
    return 0;
}

四、複雜度分析

• 時間複雜度：O(n log n)
• 空間複雜度：O(n)

樹狀數組代碼簡短、效率高，是求逆序數、區間查詢的利器。