主題
題目: 2426. Number of Pairs Satisfying Inequality
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
給兩條數字陣列 nums1, nums2 和另一個數字 diff ，問 i<j 時 nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff 總共有幾組。
解法：簡單數學移項，動態(只有加入元素)追蹤排序順序，打codeforces的用這個: https://codeforces.com/blog/entry/15729
簡單數學移項：
nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff
i 和 i 在一邊， j 和 j 在一邊，於是可以將此 2 陣列看作 1 陣列。
動態追蹤排序順序：
由於我有fake segment tree模板，懶得刻記左子樹大小的平衡樹，所以：
1. 建立 nums1[k] - nums2[k] 結果的陣列，以下簡稱 arr1 。
2. 複製一份並排序，以下簡稱此陣列為 arr2 。
3. 用 fake segment tree 做 1 維範圍搜尋。資料長度 == arr1.size() == arr2.size() 。位置 = 數字的 rank ，值 = 有幾個。
4. 從未排序的陣列左依序:
a. 看一下 arr1[k] + diff 的 rank 。利用排序好的 arr2 做二分搜可得到。
b. 用在 a 步驟得到的 rank 對那棵樹查詢 0 ~ rank ，將結果加進回傳用變數。
c. 更新那棵樹， arr1[k] 的 rank 位置增加 1 。
5. 回傳答案變數。
source code
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
給兩條數字陣列 nums1, nums2 和另一個數字 diff ，問 i<j 時 nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff 總共有幾組。
解法：簡單數學移項，動態(只有加入元素)追蹤排序順序，打codeforces的用這個: https://codeforces.com/blog/entry/15729
簡單數學移項：
nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff
i 和 i 在一邊， j 和 j 在一邊，於是可以將此 2 陣列看作 1 陣列。
動態追蹤排序順序：
由於我有fake segment tree模板，懶得刻記左子樹大小的平衡樹，所以：
1. 建立 nums1[k] - nums2[k] 結果的陣列，以下簡稱 arr1 。
2. 複製一份並排序，以下簡稱此陣列為 arr2 。
3. 用 fake segment tree 做 1 維範圍搜尋。資料長度 == arr1.size() == arr2.size() 。位置 = 數字的 rank ，值 = 有幾個。
4. 從未排序的陣列左依序:
a. 看一下 arr1[k] + diff 的 rank 。利用排序好的 arr2 做二分搜可得到。
b. 用在 a 步驟得到的 rank 對那棵樹查詢 0 ~ rank ，將結果加進回傳用變數。
c. 更新那棵樹， arr1[k] 的 rank 位置增加 1 。
5. 回傳答案變數。
source code
