UVA 11525 排列重構：樹狀數組 + 二分查找 O(k log² k) 解法

• 如排列 3 1 4 2：
• 第 1 位 3，右側比 3 小的有 {1,2} → S₁=2
• 第 2 位 1，右側比 1 小的有 {} → S₂=0
• 第 3 位 4，右側比 4 小的有 {2} → S₃=1
• 第 4 位 2，右側無數 → S₄=0

題目直接給出 S₁..Sₖ，要求重構排列。

算法：樹狀數組維護可用數字 + 二分查找第 (Sᵢ+1) 小

數據結構

• BIT 大小 k，初始 add(i, 1) 表示數字 i 可用
• sum(x) 返回 [1, x] 可用數字個數
• 查找第 t 小可用數 → 二分 sum(mid) >= t 的最小 mid

步驟

1. 初始化 BIT，所有 1~k 標記為可用
2. 對 i = 1..k：
   • 讀取 Sᵢ，目標順位 t = Sᵢ + 1
   • 二分查找最小 pos 使 sum(pos) >= t
   • ans[i] = pos，從 BIT 中移除 pos (add(pos, -1))
3. 輸出 ans[1..k]

完整代碼

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

const int MAXK = 50005;
int bit[MAXK];
int k;

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

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

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

// 找第 t 個可用數字 (1-based)
int findKth(int t) {
    int l = 1, r = k;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (sum(mid) >= t) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        cin >> k;
        fill(bit, bit + k + 1, 0);
        for (int i = 1; i <= k; ++i) add(i, 1);  // 全可用

        vector ans(k + 1);
        for (int i = 1; i <= k; ++i) {
            int s;
            cin >> s;
            ans[i] = findKth(s + 1);
            add(ans[i], -1);  // 標記已用
        }

        for (int i = 1; i <= k; ++i) {
            if (i > 1) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

複雜度分析

• 初始化：O(k log k)
• 每輪：二分 O(log k) × BIT 查詢 O(log k) = O(log² k)
• 總計：O(k log² k)，k ≤ 50000 時極快
• 空間：O(k)

優化：O(log k) 查找第 k 小

利用 BIT 內部結構直接下降查找，無需外層二分：

int findKth(int t) {
    int idx = 0;
    for (int d = 1 << 15; d; d >>= 1) {  // 2^15 > 50000
        int next = idx + d;
        if (next <= k && bit[next] < t) {
            idx = next;
            t -= bit[next];
        }
    }
    return idx + 1;
}

總複雜度降為 O(k log k)，常數極小。

相關題目

• POJ 2481 排列重構 (同類)
• LeetCode 315 計算右側小於當前元素的個數 (BIT 經典應用)
• 「順序統計樹」/ Policy-based data structure (GCC `__gnu_pbds::tree`)

總結

本題展示了因子進制表示與排列的雙向映射，結合樹狀數組動態維護順序統計，是經典的「離線查詢 + 數據結構」範式。掌握 BIT 的 findKth 優化寫法，能顯著提升競賽編程效率。