Implementação com bitset

Cada conjunto é representado por um bitset. As operações são:

• Modificar: definir o bit y do bitset x como 1.
• Consultar: calcular a quantidade de bits 1 na união dos bitsets x1 e x2.

const int MAXIMO = 1e5 + 5;
bitset<MAXIMO> conjuntos[MAXIMO];

void resolver() {
    int operacoes;
    cin >> operacoes;
    while (operacoes--) {
        int tipo, idx, valor;
        cin >> tipo >> idx >> valor;
        if (tipo == 1) {
            conjuntos[idx][valor] = 1;
        } else {
            cout << (conjuntos[idx] | conjuntos[valor]).count() << "\n";
        }
    }
}

Implementação com tabela hash

Outra abordagem para 34 pontos utiliza tabelas hash para armazenar a interseção entre pares de conjuntos. Cada valor y mantém uma lista de conjuntos que o contêm.

const int MAXIMO = 1e6 + 5;
int tamanho[MAXIMO];
unordered_map<int, int> intersecao[MAXIMO];
vector<int> contendo[MAXIMO];

void resolver() {
    int operacoes;
    cin >> operacoes;
    while (operacoes--) {
        int tipo, a, b;
        cin >> tipo >> a >> b;
        if (tipo == 1) {
            tamanho[a]++;
            for (int conj : contendo[b]) {
                int u = min(a, conj), v = max(a, conj);
                intersecao[u][v]++;
            }
            contendo[b].push_back(a);
        } else {
            if (a == b) {
                cout << tamanho[a] << "\n";
                continue;
            }
            int u = min(a, b), v = max(a, b);
            int inter = intersecao[u][v];
            cout << tamanho[a] + tamanho[b] - inter << "\n";
        }
    }
}

Solução copmleta com decomposição sqrt

A solução final combina as duas técnicas usando decomposição sqrt. Define-se um limiar B. Para valores com frequência acima de B, utiliza-se bitset; para os demais, utiliza-se tabela hash. O limiar ótimo é B = sqrt(m / w), onde w é a largura de palavra (geralmente 64).

Para evitar estouro de memória, os bitsets são alocados dinamicamente apenas quando necessário.

const int MAXIMO = 1e6 + 5;
const int LIMIAR = 8192;
const int LIMIAR_FREQ = MAXIMO / LIMIAR;

int tamanho[MAXIMO];
bitset<LIMIAR>* bitsets[MAXIMO];
unordered_map<int, int>* mapas[MAXIMO];
vector<int> contendo[MAXIMO];
int frequencia[MAXIMO], reindex[MAXIMO], total_reindex;

struct Consulta {
    int tipo, idx, valor;
} consultas[MAXIMO];

void preprocessar() {
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> consultas[i].tipo >> consultas[i].idx >> consultas[i].valor;
        if (consultas[i].tipo == 1) frequencia[consultas[i].valor]++;
    }
    total_reindex = 0;
    for (int i = 0; i < MAXIMO; i++) {
        if (frequencia[i] > LIMIAR_FREQ) reindex[i] = total_reindex++;
    }
    for (int i = 0; i < MAXIMO; i++) {
        if (frequencia[i] <= LIMIAR_FREQ) reindex[i] = total_reindex++;
    }
    for (int i = 0; i < m; i++) {
        if (consultas[i].tipo == 1) consultas[i].valor = reindex[consultas[i].valor];
    }
}

void resolver() {
    preprocessar();
    int m = ...; // carregado em preprocessar
    for (int i = 0; i < m; i++) {
        int tipo = consultas[i].tipo, idx = consultas[i].idx, valor = consultas[i].valor;
        if (tipo == 1) {
            tamanho[idx]++;
            if (valor < total_reindex) {
                if (!bitsets[idx]) bitsets[idx] = new bitset<LIMIAR>();
                (*bitsets[idx])[valor] = 1;
            } else {
                for (int conj : contendo[valor]) {
                    int u = min(idx, conj), v = max(idx, conj);
                    if (mapas[u] && mapas[u]->count(v)) (*mapas[u])[v]++;
                }
                contendo[valor].push_back(idx);
            }
        } else {
            if (idx == valor) {
                cout << tamanho[idx] << "\n";
                continue;
            }
            int inter1 = 0;
            if (mapas[idx] && mapas[idx]->count(valor)) inter1 = (*mapas[idx])[valor];
            int inter2 = 0;
            if (bitsets[idx] && bitsets[valor]) inter2 = (*bitsets[idx] & *bitsets[valor]).count();
            cout << tamanho[idx] + tamanho[valor] - inter1 - inter2 << "\n";
        }
    }
    // Limpeza: deletar objetos alocados
    for (int i = 0; i < MAXIMO; i++) {
        delete bitsets[i];
        delete mapas[i];
    }
}

Nota sobre a biblioteca pb_ds

Para usar a tabela hash cc_hash_table da biblioteca pb_ds, inclua os seguintes cabeçalhos:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;