HDU 1394 Minimum Inversion Number 解題：樹狀數組計算逆序數與循環移位

題目大意

給定 0..N-1 的一個排列。定義逆序數為 ia[j] 的對數。可進行循環左移 (首元素移至尾部)。求所有循環移位中的最小逆序數。

樹狀數組求初始逆序數

從右向左遍歷，對每個 a[i] 查詢 BIT 中 [0, a[i]-1] 的計數 (比它小且在右側的數)，累加即為逆序數。更新 BIT add(a[i], 1)。

循環移位公式推導

設初始逆序數為 inv。將首元素 x = a[0] 移至尾部：

• 原本 x 與右側所有比它小的數形成逆序對，共 x 個 (因排列為 0..N-1)。移除後逆序數減 x。
• 移至尾部後，x 與所有比它大的數 (共 N-1-x 個) 形成新逆序對。逆序數加 N-1-x。
• 新逆序數 inv' = inv - x + (N-1-x) = inv + N - 1 - 2x。

程式碼

const int MAXN = 5005;
int bit[MAXN], a[MAXN];
void add(int i, int v) { for(;i0;i-=i&-i) s+=bit[i]; return s; }

int main() {
    while (cin>>N) {
        for (int i=0;i>a[i];
        memset(bit,0,sizeof(bit));
        long long inv=0;
        for (int i=N-1;i>=0;--i) {
            inv += sum(a[i]); // a[i] 從 0 開始，BIT 從 1 開始需 +1
            add(a[i]+1, 1);
        }
        long long ans = inv;
        for (int i=0;i