二维偏序

2736. 最大和查询

给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。

对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。

返回数组 answer *，*其中 answer[i] 是第 i 个查询的答案。

示例 1：

输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
输出：[6,10,7]
解释：
对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。
对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。
对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。
因此，我们返回 [6,10,7] 。

示例 2：

输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
输出：[9,9,9]
解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。

示例 3：

输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
输出：[-1]
解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不存在答案。 

提示：

• nums1.length == nums2.length
• n == nums1.length
• 1 <= n <= 105
• 1 <= nums1[i], nums2[i] <= 109
• 1 <= queries.length <= 105
• queries[i].length == 2
• xi == queries[i][1]
• yi == queries[i][2]
• 1 <= xi, yi <= 109

二位偏序问题。

• 什么是偏序?

  形式上，偏序关系满足以下性质：

  1. 自反性（Reflexivity）：对于任意元素x，都有x ≤ x。
  2. 反对称性（Antisymmetry）：对于任意元素x和y，如果x ≤ y且y ≤ x，则x = y。
  3. 传递性（Transitivity）：对于任意元素x、y和z，如果x ≤ y且y ≤ z，则x ≤ z。

• 什么是二维偏序问题?

  二维偏序问题（Two-dimensional Partial Order Problem）是指在一个包含两个维度的数据集中，寻找一种线性排序方法来满足特定的约束条件。这种问题是组合优化和离散数学领域的一个经典问题。

  在二维偏序问题中，我们通常需要找到一个排列 P 来对数据集进行排序，使得每个元素 (x, y) 满足以下关系：

  (x1, y1) <= (x2, y2) if x1 < x2 or (x1 == x2 and y1 <= y2)

  换句话说，如果一个元素的横坐标值较小或者纵坐标值也小于等于另一个元素的对应坐标时，那么这个元素必须在前面。

对于常规的二维偏序问题的解法为: 先排序一维，再树状数组维护第二维。

class Solution:
    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        arr = sorted(set(nums2 + [y for _, y in queries]))
        mp = {v: idx + 1 for idx, v in enumerate(arr)} # 离散化
        sz = len(arr) + 1

        tree = [-1] * (len(nums1) + sz + 1)

        def low_bit(x: int) -> int:
            return x & -x

        def add(x: int, v: int) -> None:
            while x < len(tree):
                tree[x] = max(tree[x], v)
                x += low_bit(x)

        def get(x: int) -> int:
            ans = -10 ** 9
            while x > 0:
                ans = max(ans, tree[x])
                x -= low_bit(x)
            return ans

        s1 = sorted([(x, y) for x, y in zip(nums1, nums2)], key=lambda e: -e[0])
        s2 = sorted([(x, sz - mp[y], i) for i, (x, y) in enumerate(queries)], key=lambda e: -e[0])

        ans = [0] * len(queries)
        j = 0

        for i, (x, y, idx) in enumerate(s2):
            while j < len(s1) and s1[j][0] >= x:
                s, v = sum(s1[j]), sz - mp[s1[j][1]]  #把符合的都加进去
                add(v, s)
                j += 1
            ans[idx] = get(y)

        return ans