Segment Tree
Intuition\nFirst, visualize pairs (nums1, nums2) as points on a grid. In fact the problem acutally hints at this with the queries being (xi,yi)\n\n\nCreate a li
# Intuition\nFirst, visualize pairs (nums1, nums2) as points on a grid. In fact the problem acutally hints at this with the queries being (xi,yi)\n\n\nCreate a list of points, and sort them decreasingly. Then, keep track of the maximum y-coord while iterating. If the current point\'s y is greater than the current max, then keep it, else ignore it. Then update max_y. This works because the points that come later have lesser x-coordinates. Therefore, all non-redundant points will have greater y-coords. Now that all redundant points are removed, we have a very nicely ordered set of points. Due to how we defined redundant, the remaining points have the following property:\nGiven two points A and B, if A.x < B.x, then A.y > B.y, and vice versa. Also no two points have equal x or y.\n\nBecause of this, our array of points which was sorted decreasingly by x is now also sorted increasingly by y.\nNow, for each query, we can binary search for the greatest index r with a valid x value and the least index l with a valid y value. All points with index >= l has a valid y and all points with index <= r have a valid x. Therefore, all points in [l, r] are valid. Now, the problem is simply finding the maximum value of x_i + y_i for i in [l, r], which can be done easily with an RMQ or segtree.\n\n# Code\n```\nclass Solution {\npublic:\nint build(vector<int>&segment,vector<int>&sum,int l,int r,int node)\n{\n    if(l==r)\n    {\n        segment[node]=sum[l];\n        return sum[l];\n    }\n    else\n    {\n        int mid=l+r;\n        mid/=2;\n        int left=build(segment,sum,l,mid,2*node+1);\n        int right=build(segment,sum,mid+1,r,2*node+2);\n        return segment[node]=max(left,right);\n    }\n}\nint value(int ll,int rr,vector<int>&segment,int l,int r,int node)\n{\n    if(r<ll || l>rr)\n        return 0;\n    if(ll<=l && rr>=r)\n        return segment[node];\n    else\n    {\n        int mid=l+r;\n        mid/=2;\n        int le=value(ll,rr,segment,l,mid,2*node+1);\n        int ri=value(ll,rr,segment,mid+1,r,2*node+2);\n        return max(le,ri);\n    }\n}\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<pair<int,int>>v;\n        int n=nums1.size();\n        for(int i=0;i<nums1.size();i++)\n        {\n            v.push_back({nums1[i],nums2[i]});\n        }\n        sort(v.begin(),v.end());\n        reverse(v.begin(),v.end());\n        vector<pair<int,int>>p;\n        int maxi=-1;\n        for(int i=0;i<v.size();i++)\n        {\n            //cout<<v[i].first<<\' \'<<v[i].second<<endl;\n            if(v[i].second>=maxi)\n            {\n                maxi=v[i].second;\n                p.push_back({v[i].first,v[i].second});\n            }\n        }\n        int m=p.size();\n        vector<int>ans;\n        vector<int>x(m),y(m),sum(m);\n        for(int i=0;i<m;i++)\n        {\n            x[i]=p[i].first;\n            y[i]=p[i].second;\n            sum[i]=x[i]+y[i];\n        }\n        vector<int>segment(4*m+1);\n        build(segment,sum,0,m-1,0);\n        // for(int i=0;i<m;i++)\n        // cout<<x[i]<<\' \'<<y[i]<<\' \'<<sum[i]<<endl;\n        // for(int i=0;i<segment.size();i++)\n        // cout<<segment[i]<<\' \';\n        // cout<<endl;\n        for(int i=0;i<queries.size();i++)\n        {\n            int l=0,r=m-1;\n            while(l<r)\n            {\n                int mid=l+r+1;\n               // cout<<mid<<endl;\n                mid/=2;\n                if(queries[i][0]<=x[mid])\n                l=mid;\n                else\n                r=mid-1;\n            }\n          //  cout<<l<<endl;\n            r=l;\n            if(x[r]<queries[i][0])\n            {\n                ans.push_back(-1);\n                continue;\n            }\n            l=lower_bound(y.begin(),y.end(),queries[i][1])-y.begin();\n           // cout<<l<<\' \'<<r<<endl;\n            if(l>r)\n            ans.push_back(-1);\n            else\n            ans.push_back(value(l,r,segment,0,m-1,0));\n        }\n        return ans;\n    }\n};\n```
['C++']