No Segment Tree. Store "max x+y on the right" to sorted list of "y"
Approach\nLet\'s say [x,y] = [nums1[i],nums2[i]]\n1. Sort queries by "x" from big to small. When going through the queries, more and more [x,y] will become vali
# Approach\nLet\'s say [x,y] = [nums1[i],nums2[i]]\n1. Sort queries by "x" from big to small. When going through the queries, more and more [x,y] will become valid. \n2. We keep adding these new valid [x,y] into a sorted list, sort by "y" from small to big.\n3. Now the tricky part, for each y in the sorted list, we attach a value to that y. The value we attach is not "x+y", but "max x+y **on its right side**". \n4. When new "y" added to the sorted list, we update the sorted list to reflect the "max x+y on the right". A few points when updating: \n    a. If the new x+y is smaller than the "max x+y on its **right**", then the new x+y has no value for us, don\'t add it to sorted list.\n    b. Otherwise, if the new x+y is bigger than the "max x+y on its **left**", then the left "y" has no value for us anymore. Delete the left y from sorted list. \n    c. Keep doing step b until no delete. Finally, add the new "y" to sorted list.\n    Steps a,b,c are something like stack.\n\n# Code\n``` python\nfrom sortedcontainers import SortedList\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        nums = sorted([x,y] for x,y in zip(nums1,nums2))\n        A = [[x,y,i] for i,(x,y) in enumerate(queries)]\n        res = [-1]*len(queries)\n        sl_y = SortedList()\n        for x,y,i in sorted(A,reverse=True):\n            while nums and nums[-1][0]>=x:\n                x2,y2 = nums.pop()\n                ii = sl_y.bisect_left([y2,0])\n                if ii<len(sl_y) and sl_y[ii][1]>=x2+y2:\n                    continue\n                for ii2 in range(ii-1,-1,-1):\n                    if sl_y[ii2][1]<=x2+y2:\n                        sl_y.pop(ii2)\n                sl_y.add([y2,x2+y2])\n            ii = sl_y.bisect_left([y,0])\n            if ii<len(sl_y):\n                res[i] = sl_y[ii][1]\n        return res\n```
['Python3']