Method 1
You can also use a bit trie — this is a trie made of bits of your numbers, thus it is represented as a binary tree (since there are only two types of bits — 0 and 1), and its depth is $\mathcal{O}{(log(n))}$.
When you add a number, you mark the vertex that representing this particular number as a full binary tree, and then you recursively go over its parents marking them as full binary trees if their left and right children are both full binary trees as well.
When you remove a number, you unset the "full binary tree" mark and do so for all its parents.
When you want to get MEX, you should do the DFS towards $x$, avoiding visiting subtrees which are marked as full (because there are no free values in such subtrees) and attempt to visit a left subtree first if you are allowed to by the x restriction.
class MEX {
struct MEXNode {
MEXNode *children[2];
bool is_full = false;
int cnt = 0;
public:
MEXNode() {
children[0] = nullptr;
children[1] = nullptr;
}
};
private:
inline MEXNode *nonnull(MEXNode *& n) {
if (!n) n = new MEXNode();
return n;
}
void insert(int val, int level, MEXNode *n) {
if (level == -1) {
n->cnt++;
n->is_full = true;
return;
}
int cur_bit = (val & (1 << level)) >> level;
insert(val, level - 1, nonnull(n->children[cur_bit]));
n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
}
// Remove an integer from the set
void remove(int val, int level, MEXNode *n) {
if (level == -1) {
n->cnt--;
n->is_full = n->cnt > 0;
return;
}
int cur_bit = (val & (1 << level)) >> level;
remove(val, level - 1, nonnull(n->children[cur_bit]));
n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
}
// Find the minimum element >=x that isn't present in the set
int get(int val, int level, MEXNode *n) {
if (n->is_full) {
return -1;
} else if (n->cnt == 0) {
return val;
}
int cur_bit = (val & (1 << level)) >> level;
int ans = get(val, level - 1, nonnull(n->children[cur_bit]));
if (cur_bit == 0 && ans == -1) {
ans = get((val >> level << level) | (1 << level), level - 1, nonnull(n->children[1]));
}
return ans;
}
MEXNode root_node;
public:
void insert(int x) {
insert(x, 31, &root_node);
}
void remove(int x) {
remove(x, 31, &root_node);
}
int get(int x) {
return get(x, 31, &root_node);
}
};
Method 2
Create a set of intervals $S$. If the interval $[l, r]$ is present in $S$, that means that the elements $l, l + 1, l + 2, \dots , r$ are in $S$.
Adding an element $x$ is handled like this:
If $[whatever, x - 1]$ is present in the set, remove it and add $[whatever, x]$. Likewise, if $[x + 1, whatever]$ is in the set, remove it and add $[x, whatever]$.
Removals are handled in this way:
Find the interval containing x. Split it into two intervals $[start, x - 1]$, and $[x + 1, end]$.
MEX queries are handled similarly:
Find the interval containing $x$ and output $end + 1$. This can be implemented using 2 std::set<std::pair<int, int>> in C++.
The first set indexes pairs by the first element (i.e. left end), and the second one by their second element (i.e. right end)
class MEX {
typedef std::pair<int, int> interval;
std::set<interval> s[2];
std::multiset<int> values;
void insert_pair(interval p) {
auto[x, y] = p;
if (x > y) std::swap(x, y);
s[0].insert({x, y});
s[1].insert({y, x});
}
void remove_pair(interval p) {
auto[x, y] = p;
if (x > y) std::swap(x, y);
s[0].erase({x, y});
s[1].erase({y, x});
}
std::optional<interval> is_end(int x, bool left) {
int idx = left;
auto it = s[idx].lower_bound({x, 0});
if (it != s[idx].end() && it->first == x)
return *it;
else
return std::nullopt;
}
public:
void insert(int x) {
bool ok = values.find(x) == values.end();
values.insert(x);
if (!ok) return;
auto p1 = is_end(x - 1, true);
auto p2 = is_end(x + 1, false);
if (p1 && p2) {
interval i = {p1->second, p2->second};
remove_pair(*p1);
remove_pair(*p2);
insert_pair(i);
} else if (p1 && !p2) {
interval i = {p1->second, x};
remove_pair(*p1);
insert_pair(i);
} else if (!p1 && p2) {
interval i = {x, p2->second};
remove_pair(*p2);
insert_pair(i);
} else if (!p1 && !p2) {
interval i = {x, x};
insert_pair(i);
}
}
void remove(int x) {
values.erase(values.find(x));
if (values.find(x) != values.end()) return;
auto it = s[1].lower_bound({x, 0});
if (it->first != x && it->second != x) {
interval p1 = {it->second, x - 1};
interval p2 = {x + 1, it->first};
remove_pair(*it);
insert_pair(p1);
insert_pair(p2);
} else if (it->first != x && it->second == x) {
interval p = {x + 1, it->first};
remove_pair(*it);
insert_pair(p);
} else if (it->first == x && it->second == x) {
remove_pair(*it);
} else if (it->first == x && it->second != x) {
interval p = {it->second, x - 1};
remove_pair(*it);
insert_pair(p);
}
}
int get(int x) {
if (values.find(x) == values.end()) return x;
auto it = s[1].lower_bound({x, 0});
return it->first + 1;
}
};
MEX mex;
mex.insert(int);
mex.remove(int);
mex.get(int); // Find the minimum element >=x that isn't present in the set
