Sort, binary search, and get the max over ranges.
Intuition\nGetting the queries in arbitrary order is hard, but you get them all at once. So to begin with, let\'s sort the queries in descending x order. When w
# Intuition\nGetting the queries in arbitrary order is hard, but you get them all at once. So to begin with, let\'s sort the queries in descending x order. When we get a query [x, y], we need to find the max of `nums1[j] + nums2[j]` such that `nums1[j] >= x` and `nums2[j] >= y`. We store the values of the sums of pairs such that `nums2[j] >= x` exploiting the fact that we get the queries in sorted order in terms of x. Then we use binary search to only look at `j` such that `nums2[j] >= y`. We use a special data structure to then get the max of these.\n\n# Approach\nAs noted above, we sort the queries in order of `x`. We then sort `nums1` and `nums2` in order of `nums2` value. Then we maintain a special data structure that I called `MaxRangeList`, with an instance called `sums`. `MaxRangeList` maintains a list of `N` numbers, and allows setting any of those `N` numbers to a larger value, and also taking the `max` over any range of them. So e.g. if you do `sums.getRangeMax(1, 5)` that gives you the max of `sums[i]` for `1 <= i < 5`. `sums` stores the sum of `nums1[j] + nums2[j]` provided that `nums1[j] >= x` for this particular query. Otherwise `sums[j]` is set to `-float(\'inf\')` Since the x come in in sorted order, we can update this efficiently. Once we\'ve updated `sums` for a particular query, we binary search to find the smallest value of `j` such that `nums2[j] <= y`, and then `sums.getRangeMax(j, len(sums))` gives the correct answer for that query.\n\nFor a list of length `N`, `MaxRangeList` requires `O(NlogN)` initialization and memory, and each operation requires `O(logN)` time. `MaxRangeList` is very similar to the solution of the problem "Range Sum Query - Mutable", i.e. problem 307.\n\n# Complexity\n- Time complexity:\nO(nlogn) (where n is the max of len(nums1), len(nums2), and len(queries))\n\n- Space complexity:\nO(nlogn)\n\n# Code\n```\nclass TreeNode:\n    def __init__(self, val, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\n        \n\nclass MaxRangeList:\n    def __init__(self, N):\n        def build(i, j):\n            res = TreeNode([i, j, -float(\'inf\')])\n            if j == i + 1:\n                return res\n            middle = (i + j) // 2\n            res.left = build(i, middle)\n            res.right = build(middle, j)\n            return res\n        self.N = N\n        self.root = build(0, N)\n        self.items = N * [-float(\'inf\')]\n\n    def __getitem__(self, i):\n        return self.items[i]\n\n    def __setitem__(self, i, val):\n        if self[i] > val:\n            raise ValueError("Can only increase value of items")\n        def update(node):\n            if node is None:\n                return node\n            if i < node.val[0] or i >= node.val[1]:\n                return node\n            node.val[2] = max(node.val[2], val)\n            node.left = update(node.left)\n            node.right = update(node.right)\n            return node\n        self.root = update(self.root)\n\n    def getRangeMax(self, i, j):\n        def retrieve(node):\n            if node is None:\n                return -float(\'inf\')\n            if j <= node.val[0] or i >= node.val[1]:\n                return -float(\'inf\')\n            if i <= node.val[0] < node.val[1] <= j:\n                return node.val[2]\n            return max(retrieve(node.left), retrieve(node.right))\n        return retrieve(self.root)\n\n    def __len__(self):\n        return self.N\n\n\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        pairs = [(x, y) for x, y in zip(nums1, nums2)]\n        pairs.sort(key=lambda l: l[1])\n        sums = MaxRangeList(len(nums1))\n        nums1DecPairs = sorted(list(enumerate(pairs)), key=lambda l: -l[1][0])\n        queries = list(enumerate(queries))\n        res = [-1 for _ in queries]\n        queries.sort(key=lambda l: -l[1][0])\n        nums1DecIdx = 0\n        for i, (x, y) in queries:\n            while nums1DecIdx < len(nums1DecPairs) and x <= nums1DecPairs[nums1DecIdx][1][0]:\n                pairsIdx = nums1DecPairs[nums1DecIdx][0]\n                sums[pairsIdx] = sum(pairs[pairsIdx])\n                nums1DecIdx += 1\n            if y <= pairs[0][1]:\n                res[i] = sums.getRangeMax(0, len(nums1))\n                continue\n            if y > pairs[-1][1]:\n                continue\n            lo, hi = 0, len(pairs) - 1\n            while lo < hi - 1:\n                middle = (lo + hi) // 2\n                if y > pairs[middle][1]:\n                    lo = middle\n                else:\n                    hi = middle\n            res[i] = sums.getRangeMax(hi, len(nums1))\n        for i, x in enumerate(res):\n            if x == -float(\'inf\'):\n                res[i] = -1\n        return res\n```
['Python3']