HardRating 2208

1649. Create Sorted Array through Instructions

arraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set

解題說明

Create Sorted Array through Instructions

題目描述：給定整數陣列 instructions，依次將每個元素插入到一個初始為空的陣列 nums 中。每次插入的代價為 min(嚴格小於該元素的個數, 嚴格大於該元素的個數)。求所有插入的總代價，結果對 10^9 + 7 取餘。

解題思路：需要一個資料結構能高效地查詢當前陣列中小於 / 大於某值的元素個數。使用 Binary Indexed Tree (BIT / Fenwick Tree)，以數值作為索引。插入元素 x 時，小於 x 的個數為 query(x-1)，大於 x 的個數為 total - query(x)。取兩者較小值作為代價。

C++ 解法

複雜度分析

時間複雜度：O(n × log M) — 其中 n 為 instructions 長度，M 為元素最大值。每次插入和查詢的 BIT 操作為 O(log M)

空間複雜度：O(M) — BIT 陣列大小為元素最大值

虛擬碼

1. Initialize BIT with size = max value in instructions
2. For each element x in instructions (index i):
   a. less = BIT.query(x - 1)  // count of elements < x
   b. greater = i - BIT.query(x)  // count of elements > x (total - elements <= x)
   c. cost += min(less, greater)
   d. BIT.update(x, +1)
3. Return cost mod 10^9+7

其他解法

方法二：線段樹 使用線段樹代替 BIT，支援區間求和和單點更新。時間複雜度相同 O(n log M)，但常數較大且實現更複雜。

方法三：合併排序 + 逆序對統計 類似求逆序對的方式，用修改過的合併排序來計算每次插入的代價。時間複雜度 O(n log n)，但實現複雜度高。

方法四：平衡 BST（如 Order-Statistics Tree） 使用支援按秩查詢的平衡 BST（如 GNU pb_ds 的 order_of_key）。每次操作 O(log n)。C++ 中可用 __gnu_pbds::tree 實現。

延伸思考

如果元素值的範圍很大（例如 10^9），如何用離散化（coordinate compression）來優化 BIT 的空間？
BIT 和線段樹各有什麼優劣勢？在什麼情境下應該選擇哪一個？
如果允許從陣列中間刪除元素，資料結構需要如何擴展？

Create Sorted Array through Instructions — CaffeCode