Monotonic Stack || Segment Tree || C++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\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 Solution {\n    vector <int> seg;\n    void buildSGTree(int idx, int low, int high, vector <int> &sum){\n        if(low == high){\n            seg[idx] = sum[low];\n            return;\n        }\n        int mid = (low + high) >> 1;\n        buildSGTree(2*idx+1, low, mid, sum);\n        buildSGTree(2*idx+2, mid+1, high, sum);\n        seg[idx] = max(seg[2*idx+1], seg[2*idx+2]);\n    }\n    int findSum(int idx, int low, int high, int ql, int qh){\n        if(high < ql || low > qh)return -1e9;\n        if(ql <= low && high <= qh)return seg[idx];\n        int mid = (low+high) >> 1;\n        int left = findSum(2*idx+1, low, mid, ql, qh);\n        int right = findSum(2*idx+2, mid+1, high, ql, qh);\n        return max(left, right);\n    }\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector <pair <int,int>> arr;\n        for(int i = 0; i < nums1.size(); i++)arr.push_back({nums1[i], nums2[i]});\n        sort(arr.begin(), arr.end());\n        // monotonic stack...\n        stack <pair <int,int>> stk;\n        for(int i = 0; i < arr.size(); i++){\n            while(!stk.empty()){\n                if(stk.top().first == arr[i].first)stk.pop();\n                else if(stk.top().second <= arr[i].second)stk.pop();\n                else break;\n            }\n            stk.push(arr[i]);\n        }\n        cout << stk.size()<< endl;\n        vector <int> xCor, yCor, Sum, ans;\n        while(!stk.empty()){\n            int x = stk.top().first, y = stk.top().second;\n            stk.pop();\n            xCor.push_back(x);\n            yCor.push_back(y);\n            Sum.push_back(x+y);\n        }\n        reverse(xCor.begin(), xCor.end());\n        // reverse(yCor.begin(), yCor.end());\n        reverse(Sum.begin(), Sum.end());\n        // make a segment tree.. \n        // x coordinate are in increasing order... \n        // y coordinate are in decreasing order...\n        // therefore we can easily find the index in x and y coordinate..\n        // apply segment tree search and find the maximum sum between x and y\n        int sz = Sum.size();\n        seg.resize(4*sz + 1);\n        buildSGTree(0, 0, sz-1, Sum);\n        for(int i : xCor)cout << i <<" ";\n        cout << endl;\n        for(int i : yCor)cout << i <<" ";\n        cout << endl;\n\n        for(auto it : queries){\n            int x = it[0], y = it[1];\n            int x_idx = lower_bound(xCor.begin(), xCor.end(), x)-xCor.begin();\n            int y_ = lower_bound(yCor.begin(), yCor.end(), y)-yCor.begin();\n            int y_idx = (sz-1-y_);\n            cout << x_idx <<" " << y_idx << endl;\n            if(x_idx >= sz || y_idx >= sz){\n                ans.push_back(-1);\n                continue;\n            }\n            int t = findSum(0, 0, sz-1, x_idx, y_idx);\n            if(t != -1e9)ans.push_back(t);\n            else ans.push_back(-1);\n        }\n        return ans;\n    }\n};\n```
['Segment Tree', 'Monotonic Stack', 'C++']