C++ Offline Query
See my latest update in repo LeetCode\n## Offline Query\n\nA common trick for solving problems related to a series of queries. \n\nWhen we know all the queries 
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n## Offline Query\n\nA common trick for solving problems related to a series of queries. \n\nWhen we know all the queries upfront, we can sort the query and the original data in some order so that we can scan the query and the original data simultaneously (which takes `O(N + Q)` time), instead of scanning all original data for each query (which takes `O(N * Q)` time).\n\nThe name "offline" signifies the fact that we know all the queries upfront/offline. If the queries keep streaming in (i.e. online), we can\'t reorder the queries to get a better time complexity.\n\n**Problems**:\n* [1707. Maximum XOR With an Element From Array (Hard)](https://leetcode.com/problems/maximum-xor-with-an-element-from-array/)\n* [1847. Closest Room (Hard)](https://leetcode.com/problems/closest-room/)\n* [2070. Most Beautiful Item for Each Query (Medium)](https://leetcode.com/problems/most-beautiful-item-for-each-query/)\n\n## Solution 1. Offline Query\n\nSort both `items` and `queries` in ascending order of `price`. Traverse `queries`. Use a pointer `i` to cover all the items with a price `<=` the current query, and compute the maximum beauty among them. In this way, we traverse both array only once.\n\n```cpp\n// OJ: https://leetcode.com/problems/most-beautiful-item-for-each-query/\n// Author: github.com/lzl124631x\n// Time: O(NlogN + MlogM + M + N) where `N`/`M` is the length of `items`/`queries`.\n// Space: O(M)\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& A, vector<int>& Q) {\n        vector<pair<int, int>> queries;\n        for (int i = 0; i < Q.size(); ++i) queries.push_back({Q[i],i});\n        sort(begin(queries), end(queries));\n        sort(begin(A), end(A));\n        int i = 0, N = A.size(), maxBeauty = 0;\n        vector<int> ans(Q.size());\n        for (auto q : queries) {\n            auto &[query, index] = q;\n            for (; i < N && A[i][0] <= query; ++i) maxBeauty = max(maxBeauty, A[i][1]);\n            ans[index] = maxBeauty;\n        }\n        return ans;\n    }\n};\n```
[]