NYOJ 233/322 Sort：樹狀數組求逆序對數

題目大意

給定 1~n 的一個排列，每次只能交換相鄰元素，求排序為升序所需最少交換次數。即求排列的逆序對數。n ≤ 1000, T ≤ 1000。

樹狀數組 (Fenwick Tree) 解法

從左到右遍歷排列。對於當前元素 `a[i]`，已處理元素中大於它的個數即為以它為右端點的逆序對數。用樹狀數組維護值域頻率前綴和。

代碼實現 (C++)

#include 
#include 
const int MAXN = 1005;

int bit[MAXN];

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

void add(int idx, int val) {
    for (; idx < MAXN; idx += lowbit(idx)) bit[idx] += val;
}

int sum(int idx) {
    int res = 0;
    for (; idx > 0; idx -= lowbit(idx)) res += bit[idx];
    return res;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        memset(bit, 0, sizeof(bit));
        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            int x; scanf("%d", &x);
            // 已有 i-1 個數，其中 ≤x 的有 sum(x) 個，>x 的有 (i-1) - sum(x) 個
            ans += (i - 1) - sum(x);
            add(x, 1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

關鍵點

• 值域 1~n，直接作為樹狀數組下標，無需離散化。
• `add(x, 1)` 標記值 x 出現一次。
• `sum(x)` 查詢 ≤ x 的個數。
• 逆序對數可能達 n(n-1)/2 ≈ 5e5，用 `long long` 存儲。
• 多測試用例每次需 `memset` 清空 BIT。

複雜度

• 單測試：O(n log n)。
• 總體：O(T n log n) ≤ 1000 * 1000 * 10 = 1e7，極快。

替代方法

歸併排序求逆序對同樣 O(n log n)，代碼稍長但無值域限制。本題值域小，BIT 更簡潔。