Trie pentru mex

#include <bits/stdc++.h>

using namespace std;

class node {
    public:
        node *child[2];
        bool is_full = false;
        int cnt = 0;

        node() {
            child[0] = nullptr;
            child[1] = nullptr;
        }
};

node *create(node *&n) {
    if(!n)
        n = new node();
    return n;
}

void add(int val, int level, node *n) {
    if(level == -1) {
        ++n->cnt;
        n->is_full = true;
        return;
    }
    int curr_bit = (val & (1 << level)) >> level;
    add(val, level - 1, create(n->child[curr_bit]));
    n->is_full = create(n->child[0])->is_full && create(n->child[1])->is_full;
    n->cnt = create(n->child[0])->cnt + create(n->child[1])->cnt;
}

void rem(int val, int level, node *n) {
    if(level == -1) {
        --n->cnt;
        n->is_full = n->cnt > 0;
        return;
    }
    int curr_bit = (val & (1 << level)) >> level;
    rem(val, level - 1, create(n->child[curr_bit]));
    n->is_full = create(n->child[0])->is_full && create(n->child[1])->is_full;
    n->cnt = create(n->child[0])->cnt + create(n->child[1])->cnt;
}

int query(int val, int level, node *n) {
    if(n->is_full)
        return -1;
    if(n->cnt == 0)
        return val;
    int curr_bit = (val & (1 << level)) >> level;
    int ans = query(val, level - 1, create(n->child[curr_bit]));
    if(curr_bit == 0 && ans == -1)
        ans = query((val >> level << level) | (1 << level), level - 1, create(n->child[1]));
    return ans;
}

node root;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<int> a(N + 1);
    for(int i = 1; i <= M; ++i) {
        cin >> a[i];
        add(a[i], 22, &root);
    }
    int ans = query(0, 22, &root);
    for(int i = M + 1; i <= N; ++i) {
        cin >> a[i];
        rem(a[i - M], 22, &root);
        add(a[i], 22, &root);
        ans = min(ans, query(0, 22, &root));
    }
    cout << ans << '\n';
}