This is a simple way to calculate de MEX of a set of intigers x, 0 <= x <= 1e6 in O(NlogN) time. I dunno if there are some better ways, but this one come to mind in the last CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!). The fact is, imagine that you have to answer some queries at the form:

• 1: Add an integer x to the set
• 2: Remove an integer x to the set
• 3: Say what is the mex of the set

Note: The answer when there are some numbers repeated will be discussed after.

Imagine that we got an array A with all the posibles MEXs as index, and A[x] = 1 if x can be Mex, 0 otherwise. Lets go to see how to procesate the queries:

• 1: Is just to change the value in A[x] to 0. O(1) time.
• 2: Is just to change the value in A[x] to 1. O(1) time.
• 3: Find the first index i such that A[i] = 1, this is the answer. O(1e6) time in the worst case.

This is ineficcent. If you notice, that is calculate the first one, this can answered using an algoritm to calculate the k-th one, in fact, you can use any way that you know to compute this. In my case I used Segment tree, you can learn it in K-th one segment tree tutorial (Codeforces EDU)....

This is an example code:

#include <bits/stdc++.h>
#define ll long long

using namespace std;

struct SegmentTree {
  int n;
  vector<int> a;
  vector<int> tree;
 
  SegmentTree(int _n) {
    n = _n;
    a.resize(n, 1);
    a[0] = 0;
    tree.resize(n * 4);
  }
 
  void build(int node, int l, int r) {
    if (l == r) {
      tree[node] = a[l];
      return;
    }

    int mid = (l + r) / 2;

    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);

    tree[node] = tree[node * 2] + tree[node * 2 + 1]; 
  }

  void update(int node, int l, int r, int index, int value) {
    if (l == r) {
      a[index] = value;
      tree[node] = value;
      return; 
    }
 
    int mid = (l + r) / 2;
    if (index <= mid) {
      update(node * 2, l, mid, index, value);
    } else {
      update(node * 2 + 1, mid + 1, r, index, value);
    }

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
  }
 
  int query(int node, int l, int r, int k) {
    if (l == r) 
      return l;
    
    int mid = (l + r) / 2;

    if (k <= tree[node * 2]) {
      return query(2 * node, l, mid, k);
    } else {
      return query(2 * node + 1, mid + 1, r, k - tree[node * 2]);
    } 
  }
};

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int q; cin >> q;
  int MAXVALUE = 1111111;
  SegmentTree answer(MAXVALUE + 1);
  answer.build(1, 1, MAXVALUE);

  while (q --) {
    int tq; cin >> tq;

    // I use 1-indexed, then, in the segment tree, the 0 count as 1
    if (tq == 1) {
      int x; cin >> x;

      answer.update(1, 1, MAXVALUE, x + 1, 0);
    } else if (tq == 2) {
      int x; cin >> x;
  
      answer.update(1, 1, MAXVALUE, x + 1, 1);  
    } else if (tq == 3) {
      cout << answer.query(1, 1, MAXVALUE, 1) - 1 << "\n";
    }
  }

  return 0;
}

If you want to answer the same problem but with repeated numbers, you must to hold an frecuency array and only modify the structure if the frecuency of any index changes from 1 to 0 or vice versa.

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int q; cin >> q;
  int MAXVALUE = 1111111;
  SegmentTree answer(MAXVALUE + 1);
  answer.build(1, 1, MAXVALUE);

  vector<int> frecuency(MAXVALUE);

  while (q --) {
    int tq; cin >> tq;

    // I use 1-indexed, then, in the segment tree, the 0 count as 1
    if (tq == 1) {
      int x; cin >> x;

      if (frecuency[x] == 0)
        answer.update(1, 1, MAXVALUE, x + 1, 0);
      frecuency[x] ++;
    } else if (tq == 2) {
      int x; cin >> x;
  
      if (frecuency[x] == 1)
        answer.update(1, 1, MAXVALUE, x + 1, 1);  
      frecuency[x] --;
    } else if (tq == 3) {
      cout << answer.query(1, 1, MAXVALUE, 1) - 1 << "\n";
    }
  }

  return 0;
}

Sory for gramaticaly issues.