merge sort tree
Approach\n Describe your approach to solving the problem. \n Sort the first & second array without changing it\'s realtive postion.\n Now, for each query [x,y],
# Approach\n<!-- Describe your approach to solving the problem. -->\n* Sort the first & second array without changing it\'s realtive postion.\n* Now, for each query `[x,y]`, we can simply find the element which is greater than or equal to `x` in the first array by simply `lower_bound`.\n    * Let\'s assume `l` be the index after which all elements of first array is greater than or equal to `x`. \n* We can surely say that if valid pair exist then it\'d be in the range of `[l,n-1]`.\n* So, for second array create a merge sort tree and get the maximum sum in the requred range `[l,n-1` provide that element must be greater than equal to `y`.\n* We can get the maximum sum by usign lower_bound and storing suffix maximum for every range.\n\n# Complexity\n- Time complexity: $$O(q * log^2(n))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n * log(n))$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass MST{\n    private:\n        int n;\n        struct Data{int x, y, sum;};\n        vector<vector<Data>> tree;\n        vector<Data> Merge(vector<Data>&a,vector<Data>&b)\n        {\n            int l1 = a.size(), l2 = b.size(), i = 0, j = 0, k = 0;\n            vector<Data> c(l1+l2);\n            while(i < l1 && j < l2){\n                if(a[i].x < b[j].x) c[k++] = a[i++];\n                else c[k++] = b[j++];\n            }\n            while(i < l1) c[k++] = a[i++];\n            while(j < l2) c[k++] = b[j++];\n            for(int i=c.size()-2; i>-1; --i)\n                c[i].sum = max(c[i].sum,c[i+1].sum);\n            return c;\n        }\n        int query(int e,int x,int y,int l,int r,int i)\n        {\n            if(y < l || x > r) return -1;\n            if(l >= x && r <= y){\n                auto &v = tree[i];\n                Data d = {e,-1,-1};\n                int id = lower_bound(begin(v), end(v), d,\n                [](const Data& d1, const Data& d2){\n                    return d1.x < d2.x;\n                })-begin(v);\n                if(id == v.size()) return -1;\n                return v[id].sum;\n            }\n            int m = (l+r)>>1;\n            int left = query(e,x,y,l,m,2*i+1);\n            int right = query(e,x,y,m+1,r,2*i+2);\n            return max(left,right);\n        }\n        void build(int l,int r,int i,vector<pair<int,int>>&v)\n        {\n            if(l == r){\n                tree[i] = {{v[l].second,v[l].first,v[l].first+v[l].second}};\n                return;\n            }\n            int m = (l+r)>>1;\n            build(l,m,2*i+1,v);\n            build(m+1,r,2*i+2,v);\n            tree[i] = Merge(tree[2*i+1],tree[2*i+2]);\n        }\n    public:\n        MST(int n,vector<pair<int,int>>&v)\n        {\n            this->n = n;\n            tree.resize(4*n);\n            build(0,n-1,0,v);\n        }\n        int query(int x,int y,int e)\n        {\n            return query(e,x,y,0,n-1,0);\n        }\n};\n\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& A, vector<int>& B, vector<vector<int>>& Q) {\n        int n = A.size(), m = Q.size();\n        vector<int> ans;\n        vector<pair<int,int>> v(n);\n        for(int i=0; i<n; ++i) v[i] = {A[i],B[i]};\n        sort(begin(v),end(v));\n        MST mt(n,v);\n        for(auto q: Q){\n            int x = q[0], y = q[1];\n            int l = lower_bound(begin(v),end(v),make_pair(x,-1)) - begin(v);\n            int res = mt.query(l,n-1,y);\n            ans.push_back(res);\n        }\n        return ans;\n    }\n};\n```
['Array', 'Binary Search', 'Segment Tree', 'Sorting', 'Merge Sort', 'C++']