Clearly Explained - C++ Segtree
Approach\nFirst, visualize pairs (nums1, nums2) as points on a grid. In fact the problem acutally hints at this with the queries being (x_i, y_i).\n\nFrom this,
# Approach\nFirst, visualize pairs (nums1, nums2) as points on a grid. In fact the problem acutally hints at this with the queries being $$(x_i, y_i)$$.\n\nFrom this, we see there exists "redundant" points. Define a point $$A$$ as redundant if there exists another point $$B$$ such that $$A_x < B_x$$ and $$A_y$$ < $$B_y$$. This is redundant because if A is valid in the queries, so is B, and B\'s sum is greater. Therefore, we can ignore A. As such, let\'s purge these redundant points.\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\n# Complexity\n- Time complexity:\n$$O(NlogN)$$\n\n- Space complexity:\n$$O(N)$$\n\n# Code\n```\ntemplate<class T> struct Seg {\n\tconst T ID = 0; // change here\n \tT comb(T a, T b) { return max(a,b); }//change here\n\tint n; vector<T> seg;\n\tvoid init(int _n) { n = _n; seg.assign(2*n,ID); }\n\tvoid init(vector<int> arr) { \n\t\tn = arr.size(); seg.resize(2*n); \n\t\tfor(int i = 0; i<n;i++) seg[i+n] = arr[i];\n\t\tpush();\n\t}\n\tvoid pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }\n\tvoid push() { for(int i = n-1; i > 0; i--) seg[i] = comb(seg[i<<1], seg[i<<1|1]); }\n\tvoid upd(int p, T val) { // set val at position p\n\t\tseg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }\n\tT query(int l, int r) {\t// sum on interval [l, r]\n\t\tT ra = ID, rb = ID;\n\t\tfor (l += n, r += n+1; l < r; l /= 2, r /= 2) {\n\t\t\tif (l&1) ra = comb(ra,seg[l++]);\n\t\t\tif (r&1) rb = comb(seg[--r],rb);\n\t\t}\n\t\treturn comb(ra,rb);\n\t}\n};\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<pair<int, int>> g;\n        for(int i = 0 ; i < nums1.size(); i++) g.push_back({nums1[i], nums2[i]});\n        sort(g.begin(), g.end());\n        reverse(g.begin(), g.end());\n        vector<pair<int, int>> p;\n        int ymx = 0;\n        vector<int> arr;\n        for(pair<int, int> pp : g) {\n            if (pp.second > ymx){\n                ymx = pp.second;\n                p.push_back(pp);\n            }\n        }\n        int m = p.size();\n        int x[m], y[m];\n        for(int i = 0; i < m ; i++) {\n            x[i] = p[i].first;\n            y[i] = p[i].second;\n            arr.push_back(x[i] + y[i]);    \n        }\n        Seg<int> st;\n        st.init(arr);\n        vector<int> re;\n        for(vector<int>& q : queries){\n            int ll =0, rr = m-1;\n            while(ll < rr){\n                int m = (ll+rr+1)/2;\n                if (x[m] >= q[0]) ll = m;\n                else rr = m-1;\n            }\n            int r = ll;\n            if (x[r] < q[0]) r = -1; \n            int l = lower_bound(y, y+m, q[1]) - y;\n            if(l > r) re.push_back(-1);\n            else re.push_back(st.query(l, r));\n        }\n        return re;\n        \n    }\n};\n```
['C++']