我怎样才能优化下面的程序？

Question

给你一个长度为N的数组A。对于任何给定的整数X，你需要找到一个严格大于X的整数Z，使得Z不在数组A中。你需要最小化Z的值。

输入：

第一行:两个空格分隔的整数N和Q，分别表示数组A中的元素数和查询数

第二行:表示数组元素的n个空间分隔的整数

接下来的Q行:每行由一个整数X组成

输出:打印q行，每行表示对相应查询的回答。

示例输入：

5 2
2 7 5 9 15
3
9

示例输出：

4
10

来源- https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/practice-problems/algorithm/yet-to-keep-6f89250c/description/

我的解决方案是-

int main()
{
    ll n,q;
    cin>>n>>q;
    map<ll,bool>mp;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin>>x;
        mp[x]=true;
    }
    while(q--)
    {
        ll x;
        cin>>x;
        x++;
        while(mp[x])
        {
            x++;
        }
        cout<<x<<endl;
    }
}

Answer 1

你的查询复杂度是O(n)*(Z-X)，

您可能已经使用以下命令转换为O(n)+(Z-X)：

ll x;
std::cin >> x;
x++;
auto it = mp.find(x);
if (it != mp.end()) {
    while (it != mp.end() && it->first == x) {
        ++it;
        ++x;
    }
}
std::cout << x << std::endl;

但我认为在预处理中构建间隔将允许更好的性能(O(log(Intervals)))。