Hard
493. Reverse Pairs
arraybinary-searchdivide-and-conquerbinary-indexed-treesegment-treemerge-sortordered-set
解題說明
Reverse Pairs
題目描述：給定一個整數陣列 nums，計算「重要逆序對」的數量。重要逆序對定義為 i < j 且 nums[i] > 2 * nums[j]。
解題思路：利用歸併排序的分治策略。在合併兩個已排序的子陣列之前，先用雙指標計算跨越左右半段的重要逆序對數量。由於左右兩半已各自排序，對於左半段的每個元素 nums[i]，右半段中滿足 nums[i] > 2 * nums[j] 的 j 形成一個前綴，且隨 i 增大此前綴只會增長（單調性）。因此雙指標掃描的總時間為 O(n)。加上歸併排序本身的 O(n log n)，總時間為 O(n log n)。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 歸併排序的分治結構，每層合併和計數均為 O(n)，共 O(log n) 層。
空間複雜度：O(n) — 歸併排序所需的暫存空間。
虛擬碼
1. Define mergeSort(nums, lo, hi):
a. Base case: if lo >= hi, return 0
b. mid = (lo + hi) / 2
c. count = mergeSort(nums, lo, mid) + mergeSort(nums, mid+1, hi)
d. Count cross pairs with two pointers:
- j = mid + 1
- For each i in [lo, mid]:
- While j <= hi and nums[i] > 2 * nums[j]: j++
- count += j - (mid + 1)
e. Merge nums[lo..mid] and nums[mid+1..hi]
f. Return count
2. Return mergeSort(nums, 0, n-1)其他解法
BIT + 離散化 O(n log n)：將所有值和其二倍值離散化。從右到左遍歷，對每個 nums[i]，在 BIT 中查詢小於 nums[i]/2 的元素數量（即之前插入的 j > i 中 nums[j] < nums[i]/2 的個數），然後將 nums[i] 插入 BIT。
BST / 平衡樹 O(n log n)：使用平衡二元搜尋樹（如 AVL 或紅黑樹），從右到左遍歷，每次查詢小於 nums[i]/2 的節點數量後插入 nums[i]。但 C++ STL 的 set/map 不直接支援 order statistics，需要使用 policy-based tree 或手寫。
延伸思考
- 如果條件改為 nums[i] > k * nums[j]（k 為任意常數），方法是否仍然適用？
- 這個問題與經典的逆序對計數（i < j 且 nums[i] > nums[j]）有何異同？
- 能否用 CDQ 分治（陳丹琦分治）來解決此問題？