HDU 4911 Inversion：逆序對 + 樹狀數組離散化

問題描述

給定長度 n 的序列（可重複），可進行最多 k 次相鄰交換。求交換後最少剩餘逆序對數。

每次相鄰交換可減少最多 1 個逆序對，因此答案 = max(0, 總逆序對數 - k)。核心任務：計算初始逆序對數。

解題思路：樹狀數組 (BIT) + 離散化

1. 離散化：將序列值映射到 1..m（m ≤ n），保持相對大小。可用 sort + unique 或 stable_sort 保持相等元素原序（不影響逆序對計數）。
2. BIT 計數：從左到右掃描，對每個 a[i]，查詢已出現的 > a[i] 的個數 = i-1 - sum(a[i])。累加得總逆序對。然後 add(a[i], 1)。
3. 結果：ans = max(0LL, inv - k)。

關鍵代碼片段 (C++)

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

struct BIT {
    vector<int> t;
    BIT(int n=0) { init(n); }
    void init(int n) { t.assign(n+1, 0); }
    void add(int i, int v) { for (; i < (int)t.size(); i += i&-i) t[i] += v; }
    int sum(int i) { int s=0; for(; i>0; i-=i&-i) s+=t[i]; return s; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; LL k;
    while (cin >> n >> k) {
        vector<int> a(n), vals(n);
        for (int i = 0; i < n; ++i) { cin >> a[i]; vals[i] = a[i]; }
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        for (int &x : a) x = lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
        BIT bit(vals.size());
        LL inv = 0;
        for (int i = 0; i < n; ++i) {
            inv += i - bit.sum(a[i]);
            bit.add(a[i], 1);
        }
        cout << max(0LL, inv - k) << '\n';
    }
    return 0;
}

複雜度分析

• 離散化 O(n log n)，BIT 操作 O(n log n)。
• 總時間 O(n log n)，空間 O(n)。
• n ≤ 100,000，inv 可能達 ~5×10^9，需 long long。

總結

HDU 4911 核心是經典逆序對計數，離散化 + BIT 是標準解法。題目額外給出 k 次交換機會，利用「每次相鄰交換最多減 1 個逆序對」的性質直接扣除。注意 stable_sort 可省去顯式去重邏輯，但 sort+unique+lower_bound 更通用直觀。