Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nhttps://leetcode.com/problems/maximum-sum-queries/solutions/3623933/clearly-explained
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nhttps://leetcode.com/problems/maximum-sum-queries/solutions/3623933/clearly-explained-c-segtree/\n\nIf we arrange {nums1, nums2} on a grid, we can see that there are some useless points because there are other points for which both coordinates are larger.\n\nTo eliminate these coordinates, we sort the array of elementwise pairs of nums1 and nums2 in decreasing order.\n\nNow, iterating over the array, x is decreasing, while y can increase if a large y is paired with a small x. \n\nSo we can remove the useless points by tracking the maximum y seen so far and keeping the element only if the y value exceeds the maximum y seen so far.\n\nAfter we have removed all the useless elements, the resulting array has a nice property that it is decreasing in x and increasing in y.\n\nSo for each query, we can binary search for the last element j such that x is viable and for the first element i such that y is viable.\n\nWe want [i..n-1] to overlap with [0..j] and so finally we want to search for the max value in [i,j]. We can do this with max segment tree, the underlying values of segment tree is the sum of the useful pairs in the array of useful numbers.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SegTree{\n    public:\n    vector<int> t;\n    SegTree(int n)\n    {\n        t.assign(4*n, -1);\n    }\n\n    void point_update(int i, int l, int r, int pos, int val)\n    {\n        if(pos < l || pos > r)\n        {\n            return;\n        }\n\n        if(l == r)\n        {\n            t[i] = val;\n            return;\n        }\n\n        int mid = l + (r-l)/2;\n        point_update(2*i, l, mid, pos, val);\n        point_update(2*i + 1, mid+1, r, pos, val);\n        t[i] = max(t[2*i], t[2*i+1]);\n    }\n\n    int range_query(int i, int lq, int rq, int l, int r)\n    {\n        if(lq > rq || r < lq || l > rq)\n        {\n            return -1;\n        }\n\n        if(lq <= l && r <= rq)\n        {\n            return t[i];\n        }\n\n        int mid = l + (r-l)/2;\n        return max(range_query(2*i, lq, rq, l, mid),\n                    range_query(2*i + 1, lq, rq, mid+1, r));\n    }\n\n};\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<vector<int>> nums;\n\n        for(int i = 0; i<nums1.size(); i++)\n        {\n            int x = nums1[i];\n            int y = nums2[i];\n            nums.push_back({x, y});\n        }\n\n        sort(nums.begin(), nums.end());\n\n        reverse(nums.begin(), nums.end());\n\n        vector<vector<int>> goodnums;\n        int max_y = 0;\n\n        for(int i = 0; i<nums.size(); i++)\n        {\n            int x = nums[i][0];\n            int y = nums[i][1];\n            if(max_y >= y)\n            {\n                continue;\n            }\n            else\n            {\n                max_y = y;\n                goodnums.push_back(nums[i]);\n                \n            }\n        }\n\n        // good nums has x in decreasing order, we can bsearch to find the first position with large enough x,\n        // this also forces nums to have increasing y\n        // we can bsearch the smallest y that is valid, now we have to search for the max x+y in the region\n        int n = goodnums.size();\n        SegTree st(n);\n\n        for(int i = 0; i<goodnums.size(); i++)\n        {\n            int x = goodnums[i][0];\n            int y = goodnums[i][1];\n            st.point_update(1, 0, n-1, i, x+y);\n        }\n\n        vector<int> res;\n\n        for(int i = 0; i<queries.size(); i++)\n        {\n            int x = queries[i][0];\n            int y = queries[i][1];\n\n            \n\n            int lo = 0;\n            int hi = n-1;\n            int ans1 = -1;\n\n            while(lo <= hi)\n            {\n                int mid = lo + (hi - lo)/2;\n                // find the largest position for which x works, since decreasing in x\n                if(goodnums[mid][0] >= x)\n                {\n                    ans1 = mid;\n                    lo = mid+1;\n                }\n                else\n                {\n                    hi = mid-1;\n                }\n            }\n\n            if(ans1 == -1)\n            {\n                res.push_back(-1);\n                continue;\n            }\n\n            lo = 0;\n            hi = n-1;\n            int ans2 = -1;\n\n            while(lo <= hi)\n            {\n                int mid = lo + (hi - lo)/2;\n                // find the smallest index for which y works, since increasing in y\n                if(goodnums[mid][1] >= y)\n                {\n                    ans2 = mid;\n                    hi = mid - 1;\n                }\n                else\n                {\n                    lo = mid + 1;\n                }\n            }\n\n            if(ans2 == -1)\n            {\n                res.push_back(-1);\n                continue;\n            }\n\n            res.push_back(st.range_query(1, ans2, ans1, 0, n-1));\n        }\n\n        return res;\n    }\n};\n```
['C++']