HardRating 2533
2736. Maximum Sum Queries
arraybinary-searchstackbinary-indexed-treesegment-treesortingmonotonic-stack
解題說明
Maximum Sum Queries
題目描述： 給定兩個等長整數陣列 nums1 和 nums2，以及一組查詢 queries。每個查詢 [xi, yi] 要求找到 nums1[j] + nums2[j] 的最大值，其中 j 滿足 nums1[j] >= xi 且 nums2[j] >= yi。若不存在返回 -1。
解題思路： 離線處理：將索引 j 按 nums1[j] 降序排列，查詢按 xi 降序排列。遍歷查詢時，將所有 nums1[j] >= xi 的索引加入，然後在已加入的索引中找 nums2[j] >= yi 且 nums1[j] + nums2[j] 最大的。
加入元素時維護一個單調棧：按 nums2[j] 排序，棧中的和值遞減。這樣查詢 nums2[j] >= yi 時，二分搜尋找到第一個 nums2[j] >= yi 的位置，其和值即為答案（因為棧是遞減的）。
C++ 解法
複雜度分析
時間複雜度：O((n + m) log n) — 排序 O(n log n + m log m)，單調棧攤銷 O(n)，每次查詢二分搜尋 O(log n)
空間複雜度：O(n + m) — 排序輔助陣列和單調棧
虛擬碼
1. Sort indices by nums1 descending
2. Sort queries by xi descending (keep original index)
3. Initialize empty monotonic stack
4. For each query (xi, yi) in descending xi order:
a. Add all elements with nums1[j] >= xi to stack
- Maintain: stack sorted by nums2 ascending, sum descending
- Remove dominated entries (smaller nums2 AND smaller sum)
b. Binary search stack for first entry with nums2 >= yi
c. If found, answer = that entry's sum; else -1
5. Return answers in original query order其他解法
-
線段樹 + 離散化法：將 nums2 離散化，用線段樹維護 [yi, max] 區間的最大和值。每次加入元素時更新線段樹，查詢時區間查詢最大值。時間 O((n+m) log n)。
-
BIT + 離散化法：類似線段樹法但用 BIT 維護後綴最大值。需要倒序處理 nums2 維度。時間複雜度相同但常數更小。
延伸思考
- 如果查詢改為在線的（不能離線排序），如何用持久化線段樹解決？
- 如果要求的是最小和而非最大和，單調棧的維護方式需要如何改變？
- 如果條件改為三維（nums1[j] >= xi, nums2[j] >= yi, nums3[j] >= zi），有什麼高效做法？