RRAHSEM - Editorial

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define x first
#define y second
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI (atan(1)*4)
#define mp make_pair
using namespace std;




const int maxn = 2e5 + 1;

int N = maxn;
int component[maxn], weight[maxn];

inline int root(int x) {
    while (component[x] != x) {
        component[x] = component[component[x]];
        x = component[x];
    }
    return x;
}

inline bool same(int x, int y) {
    return root(x) == root(y);
}

inline void merge(int x, int y) {
    if (same(x, y))
        return;
    x = root(x);
    y = root(y);
    if (weight[x] < weight[y])
        swap(x, y);
    weight[x] += weight[y];
    component[y] = x;
}


//end of DSU

//mapper
int ptr;

int freq[maxn], grouped[maxn], n, groups, pos1, pos2;
ll val1, val2, shift[60];


struct trie {
    trie* nxt[10];
    int val;
    trie() {
        for (register int i = 0; i < 10; i++)
            nxt[i] = NULL;
        val = 0;
    }
};

trie* rt;


inline int getval(register ll num) {
    trie* node = rt;
    int nxt;
    while (num) {
        nxt = num % 10;
        num /= 10;
        if (node->nxt[nxt] == NULL)
            return 0;
        node = node->nxt[nxt];
        if (num == 0)
            return node->val;
    }
    return 0;
}

inline void putval(register ll num, int val) {
    trie* node = rt;
    int nxt;
    while (num) {
        nxt = num % 10;
        num /= 10;
        if (node->nxt[nxt] == NULL)
            node->nxt[nxt] = new trie();
        node = node->nxt[nxt];
    }
    node->val = val;
}

int main()
{
    fastread;
    shift[0] = 1;
    for (int i = 1; i < 60; i++)
        shift[i] = 2 * shift[i - 1];
    rt = new trie();
    cin >> n;
    for (int i = 1; i <= n; i++) {
        component[i] = i;
        weight[i] = 1;
    }
    for (int i = 0; i < n; i++) {
        cin >> val1;
        pos1 = getval(val1);
        if (pos1 == 0) {
            ptr++;
            pos1 = ptr;
            putval(val1, ptr);
            freq[pos1]++;
            groups++;

        }
        else if (grouped[pos1]) {
            cout << groups << '\n';
            continue;
        }
        else {
            freq[pos1]++;
            groups++;
            cout << groups << '\n';
            continue;
        }
        for (int j = 0; j < 60; j++) {
            val2 = val1 ^ shift[j];
            pos2 = getval(val2);
            if (pos2 == 0 || same(pos1, pos2))
                continue;
            groups -= freq[pos2];
            grouped[pos2] = 1;
            grouped[pos1] = 1;
            freq[pos2] = 1;
            freq[pos1] = 1;
            merge(pos1, pos2);
        }
        cout << groups << '\n';
    }
    return 0;
}