### SN0WM4N's blog

By SN0WM4N, history, 12 days ago, 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;
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;

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;

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. mex, Comments (4)
 » Fun fact: https://en.wikipedia.org/wiki/Van_Emde_Boas_tree this structure supports O(log(log(N))) operations but I'm not sure how much better that is in practice.
 » Auto comment: topic has been updated by SN0WM4N (previous revision, new revision, compare).
 » 12 days ago, # | ← Rev. 2 →   One could use std::set instead of a segment tree to store all the numbers up to n that do NOT appear in the set, and the answer would be just the smallest element in this set (if we know that the size of the set is always at most n, otherwise we could use some doubling argument similar to the implementation of std::vector).
•  » » Oh. Thats right, thanks.