Please tell me the efficient algorithm of Range Mex Query

Question

I have a question about this problem.

Question

• You are given a sequence a[0], a 1],..., a[N-1], and set of range (l[i], r[i]) (0 <= i <= Q - 1).
• Calculate mex(a[l[i]], a[l[i] + 1],..., a[r[i] - 1]) for all (l[i], r[i]).

The function mex is minimum excluded value.
Wikipedia Page of mex function

You can assume that N <= 100000, Q <= 100000, and a[i] <= 100000.
O(N * (r[i] - l[i]) log(r[i] - l[i]) ) algorithm is obvious, but it is not efficient.

My Current Approach

#include <bits/stdc++.h>
using namespace std;
int N, Q, a[100009], l, r;
int main() {
    cin >> N >> Q;
    for(int i = 0; i < N; i++) cin >> a[i];
    for(int i = 0; i < Q; i++) {
        cin >> l >> r;
        set<int> s;
        for(int j = l; j < r; j++) s.insert(a[i]);
        int ret = 0;
        while(s.count(ret)) ret++;
        cout << ret << endl;
    }
    return 0;
}

Please tell me how to solve.

EDIT: O(N^2) is slow. Please tell me more fast algorithm.

Answer 1

Here's an O((Q + N) log N) solution:

1. Let's iterate over all positions in the array from left to right and store the last occurrences for each value in a segment tree (the segment tree should store the minimum in each node).

2. After adding the i-th number, we can answer all queries with the right border equal to i.

3. The answer is the smallest value x such that last[x] < l. We can find by going down the segment tree starting from the root (if the minimum in the left child is smaller than l, we go there. Otherwise, we go to the right child).

That's it.

Here is some pseudocode:

tree = new SegmentTree() // A minimum segment tree with -1 in each position
for i = 0 .. n - 1
    tree.put(a[i], i)
    for all queries with r = i
         ans for this query = tree.findFirstSmaller(l)

The find smaller function goes like this:

int findFirstSmaller(node, value)
    if node.isLeaf()
        return node.position()
    if node.leftChild.minimum < value
        return findFirstSmaller(node.leftChild, value)
    return findFirstSmaller(node.rightChild)

This solution is rather easy to code (all you need is a point update and the findFisrtSmaller function shown above and I'm sure that it's fast enough for the given constraints.