Dominating coordinates || Beats 98.5% || With comments || Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nWe use a concept of dominating coordinates to solve this problem, which is well explain
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe use a concept of dominating coordinates to solve this problem, which is well explained in this video by Vivek Gupta. https://www.youtube.com/watch?v=NoEtwEeLGNI\n\n******This video does not belong to me*****\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nBasic idea is to generate a list of relevant coordinates (explained in the above video) which form a pattern wherein x coords are in inc order while y coords are in dec order.\nSo for the sum of these pairs we generate a segment tree and for each query we find the relevant x index and y index using binary search.\nSince x is increasing and y is decresing for the pairs these indices form the l and r for our seg tree query.\nThe answer of this query will be the max Sum for the given x and y.\n\n# Complexity\n- Time complexity: O((Q + N) logN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(4*N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SGTree {\n\tvector<int> seg;\n\npublic:\n\tSGTree(int n) {\n\t\tseg.resize(4 * n + 1);\n\t}\n\n\tvoid build(int index, int low, int high, vector<int> &arr) {\n\t\tif (low == high) {\n\t\t\tseg[index] = arr[low];\n\t\t\treturn;\n\t\t}\n\n\t\tint mid = (low + high) >> 1;\n\t\tbuild(2 * index + 1, low, mid, arr);\n\t\tbuild(2 * index + 2, mid + 1, high, arr);\n\n\t\tseg[index] = max(seg[2 * index + 1], seg[2 * index + 2]);\n\t\treturn;\n\t}\n\n\tint query(int index, int low, int high, int l, int r) {\n\t\t// no overlap\n\t\t// [l r low high] or [low high l r]\n\t\tif (r < low || high < l) return INT_MIN;\n\n\t\t// complete overlap\n\t\t// [l low high r]\n\t\tif (low >= l && high <= r) return seg[index];\n\n\t\t// partial overlap\n\t\t// call query rec func on left and right\n\t\tint mid = (low + high) >> 1;\n\t\tint left = query(2 * index + 1, low, mid, l, r);\n\t\tint right = query(2 * index + 2, mid + 1, high, l, r);\n\t\treturn max(left, right);\n\t}\n\n    int root() {\n        return seg[0];\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        int n = nums1.size();\n        vector<pair<int, int>> points(n);\n        for(int i=0; i<n; i++) {\n            points[i] = {nums1[i], nums2[i]};\n        }\n\n        sort(points.begin(), points.end());\n        \n        // excluding the elements that are being dominated i.e. next element has x>= curX and y >= curY\n        vector<pair<int, int>> p;\n        for(int i=0; i<n; i++) {\n            while(!p.empty() && (p.back().first <= points[i].first && p.back().second <= points[i].second)) {\n                p.pop_back();\n            }\n            p.push_back(points[i]);\n        }\n\n        // now we have all dominating points in p with x in increasing order and y in decreasing order and now we can create a seg tree \n        // with the sum of these points\n        vector<int> sum, xArr, yArr;\n        for(auto it: p) {\n            sum.push_back(it.first + it.second);\n            xArr.push_back(it.first);\n            yArr.push_back(it.second);\n        }\n\n        // since in xArr x is in inc order and y is in dec order in yarr we need index from which x is >= q[0](left to right) and \n        // index from right to left form which y >= q[1]\n\n        // to avoid reversing y everytime to find lower bound we can reverse y and find lower bound and subtract n from it to get \n        // the effective r for range query of the seg tree\n        reverse(yArr.begin(), yArr.end());\n\n        // building seg tree of sum vector\n        n = sum.size();\n        SGTree sgt(n);\n        sgt.build(0, 0, n-1, sum);\n\n        vector<int> ans;\n\n        for(auto q: queries) {\n            // since in xArr x is in inc order and y is in dec order in yarr (but reversed to find lower bound) we need index from which \n            // x is >= q[0](left to right) and \n            // index from right to left form which y >= q[1]\n\n            auto xIt = lower_bound(xArr.begin(), xArr.end(), q[0]);\n            if (xIt == xArr.end()){\n                ans.push_back(-1); // no element greater or equal\n                continue;\n            }\n            int x = xIt - xArr.begin();\n\n            auto yIt = lower_bound(yArr.begin(), yArr.end(), q[1]);\n            if (yIt == yArr.end()) {\n                ans.push_back(-1); // no element greater or equal\n                continue;\n            }\n            int y = yIt - yArr.begin();\n            y = n - 1 - y; // since yArr was reversed, calculating the effective index of y for query\n\n            int curSum = x<=y ? sgt.query(0, 0, n-1, x, y) : -1;\n            ans.push_back(curSum);\n        }\n\n        return ans;\n    }\n};\n```
['Segment Tree', 'Monotonic Stack', 'C++']