HardRating 2053
3072. Distribute Elements Into Two Arrays II
arraybinary-indexed-treesegment-treesimulation
解題說明
Distribute Elements Into Two Arrays II
題目描述：給定一個整數陣列 nums，將元素依序分配到兩個陣列 arr1 和 arr2。第一個元素放入 arr1，第二個放入 arr2。之後每個元素根據 greaterCount(arr, val) 的比較結果決定放入哪個陣列：若 arr1 中嚴格大於 val 的元素數量嚴格大於 arr2 中的，則放入 arr1；反之放入 arr2；相等時放入 arr1。最終回傳 arr1 和 arr2 的連接結果。
解題思路：關鍵在於高效計算 greaterCount——陣列中嚴格大於某值的元素數量。使用離散化 + 樹狀陣列（Binary Indexed Tree, BIT）。先對所有數值離散化，為 arr1 和 arr2 各維護一個 BIT，支援單點更新和前綴查詢。greaterCount(arr, val) = 總元素數 - 前綴和(val 對應的離散化位置)，即可在 O(log n) 時間內完成。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 離散化排序 O(n log n)，每次插入和查詢 BIT 為 O(log n)，共 n 次。
空間複雜度：O(n) — BIT 和離散化陣列各使用 O(n) 空間。
虛擬碼
1. Coordinate-compress all values in nums 2. Create two BITs (one for arr1, one for arr2) 3. Place nums[0] in arr1, nums[1] in arr2; update respective BITs 4. For i = 2 to n-1: a. Compute greaterCount1 = arr1.size - BIT1.query(compressed index of nums[i]) b. Compute greaterCount2 = arr2.size - BIT2.query(compressed index of nums[i]) c. If greaterCount1 > greaterCount2, or they are equal: add to arr1 d. Else: add to arr2 e. Update the corresponding BIT 5. Return arr1 concatenated with arr2
其他解法
線段樹 O(n log n)：用線段樹替代 BIT，支援相同的區間查詢操作。實作稍複雜但功能更強大（例如可以支援區間最值查詢）。
平衡二叉搜尋樹（如 std::set + order_of_key）O(n log n)：使用 GNU Policy-Based Data Structure 的 tree<int, null_type, ...> 可直接呼叫 order_of_key 計算排名。程式碼更簡潔但依賴 GCC 擴展。
延伸思考
- 如果分配規則改為「嚴格小於 val 的元素數量」，演算法需要如何調整？
- 如果要分配到 k 個陣列（而非兩個），如何擴展資料結構？
- 如果元素是動態插入和刪除的（而非一次性），BIT 還適用嗎？