HardRating 2030

2426. Number of Pairs Satisfying Inequality

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

解題說明

Number of Pairs Satisfying Inequality

題目描述：給定兩個整數陣列 nums1 和 nums2（長度相同）以及整數 diff，計算滿足 nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff 且 i < j 的索引對 (i, j) 數量。

解題思路：首先化簡不等式：令 a[i] = nums1[i] - nums2[i]，則條件變為 a[i] - a[j] <= diff，即 a[i] <= a[j] + diff（其中 i < j）。

問題轉化為：對於陣列 a，計算有多少對 (i, j)（i < j）滿足 a[i] <= a[j] + diff。

可以用歸併排序（類似逆序對計數）來解決。在合併過程中，對於右半部分的每個元素 a[j]，統計左半部分中有多少元素 a[i] <= a[j] + diff。

C++ 解法

複雜度分析

時間複雜度：O(n log n) — 歸併排序的時間複雜度

空間複雜度：O(n) — 歸併排序需要的額外空間

虛擬碼

1. Compute a[i] = nums1[i] - nums2[i] for all i
2. Perform merge sort on array a:
   a. Recursively sort left half and right half
   b. Before merging, count valid pairs:
      - For each j in right half, count i in left half where a[i] <= a[j] + diff
      - Use two pointers since both halves are sorted
   c. Merge the two sorted halves
3. Return total count

其他解法

BIT（樹狀陣列）+ 座標壓縮：從左到右遍歷，對於每個 j，查詢 BIT 中 <= a[j] + diff 的元素數量，然後將 a[j] 插入 BIT。需要先對值進行座標壓縮。時間複雜度 O(n log n)。
線段樹法：類似 BIT 但使用線段樹維護值域上的計數。可以直接區間查詢 [min, a[j]+diff] 的元素數量。時間複雜度 O(n log n)，常數較大。

延伸思考

如果不等式改為嚴格小於（a[i] < a[j] + diff），計數方式需要如何調整？
如果要找滿足條件的所有對的索引列表，如何修改歸併排序？
如果 diff 會變化（多次查詢不同的 diff），如何預處理以加速？

Number of Pairs Satisfying Inequality — CaffeCode