§ Data structure to maintain mex

§ offline

• Key idea: maintain a set of numbers that we have not seen, and maintain set of numbers we have seen. Update the set of unseen numbers on queries. The mex is the smallest number of this set.

§ online

• Key idea: exploit cofinality. Decompose set of numbers we have not seen into two parts: a finitary part that we maintain, and the rest of the infinite part marked by an int that tells us where the infinite part begins.

set<int> unseen;
map<int, int> freq;
// unseen as a data structure maintains
// information about [0..largest_ever_seen]
int largest_ever_seen;


void init() {
    unseen.insert(0);
}

void mex_insert(int k) {
    freq[k]++;
    for(int i = largest_ever_seen+1; i <= k; ++i) {
        unseen.insert(i);
    }
    unseen.erase(k);
    largest_ever_seen = max(largest_ever_seen, k);
}

void mex_delete(int k) {
    assert(freq[k] >= 1);
    freq[k]--;
    if (freq[k] == 0) {
        unseen.insert(k);
    }
}

int mex_mex() {
    assert(!unseen.empty());
    return *unseen.begin();
}