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

Question

输入：

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

第二行：N个表示数组元素的分隔整数

5 2
2 7 5 9 15
3
9

4
10

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)))。