Consultas XOR en un conjunto dado

Dado un conjunto S con el elemento inicial 0 que es S = { 0 }. La tarea es realizar cada consulta cuando se da Q número de consultas e imprimir la respuesta después de cada consulta de tipo 3. 
Podemos realizar tres tipos de operaciones de consulta: 
 

• 1 X: Podemos sumar X al conjunto S.
• 2 Y: Para cada elemento i, realice i ⊕ Y.
• 3: Encuentra el elemento mínimo del conjunto.

Ejemplos: 
 

Entrada: Q = 10, 
3 
1 7 
3 
2 4 
2 8 
2 3 
1 10 
1 3 
3 
2 1 
Salida: 0 0 3
Explicación: 
Para las 10 consultas dadas, los cambios en el conjunto para cada consulta son los siguientes: 
 

1. El mínimo es 0.
2. El número 7 sumado a S –> {0, 7}.
3. El mínimo sigue siendo 0.
4. Todos los números en S se cambian a su xor con 4 -> {4, 3}.
5. Todos los números en S se cambian a su xor con 8 -> {12, 11}.
6. Todos los números en S se cambian a su xor con 3 -> {15, 8}.
7. El número 10 sumado a S –> {15, 8 ,10}.
8. El número 3 sumado a S –> {15, 8, 10, 3}.
9. El mínimo ahora es 3.
10. Todos los números en S se cambian a su xor con 1 -> {14, 9, 11, 2}.

Entrada: Q = 6 
3 
1 7 
3 
1 4 
2 8 
3 
Salida: 0 0 8 
 

Prerrequisito: Trie .
Enfoque: 
Intentaremos resolver este problema utilizando el enfoque trie del Problema  de par de valor XOR mínimo .
 

• Entonces, en este problema, tenemos un trie binario y un entero x, tenemos que encontrar el valor mínimo de XOR(x, y) donde y es un número entero del trie. 
   
• Ahora, para resolver este problema, descenderemos de la parte más significativa a la más pequeña. 
   
• Supongamos que estamos en i-ésimo bit: 
  si x[i] es 1, seguiremos el camino del trie que tiene 1. 
  Si x[i] es 0, seguiremos el camino que tiene 0. 
  Si en la posición i , no tenemos una rama para bajar x[i], iremos por el otro lado. 
   

Ahora, llegando a nuestro problema. 
 

• Supongamos que hemos insertado a1, a2, a3 en el conjunto y luego xor todo con x1, x2, x3, entonces es lo mismo que XOR-ing con X = XOR(x1, x2, x3). 
   
• Entonces, encontrar el elemento mínimo es equivalente a encontrar el mínimo entre (a1, a2, a3) después de XOR-ing con X. 
  Ya hemos notado cómo hacerlo al principio. 
   
• Ahora, cómo responder a cada una de las consultas. 
  Sea x = XOR(x1, x2, ….., xn), donde x1, x2, …, xn son todos los números a los que se les pide XOR con el elemento del conjunto S. 
  1. Para la Consulta 2 , XOR con xi. 
     no haremos XOR cada elemento en el trie con xi. en su lugar, solo actualizaremos x = XOR(x, xi) 
      
  2. Para la consulta 3 , obteniendo el elemento mínimo. 
     Se suponía que teníamos que aplicar XOR a toda la array hasta ahora con X. 
     Entonces, ahora solo calcularemos el valor mínimo obtenido al tomar XOR de todos los elementos en el conjunto con X usando el enfoque mencionado anteriormente. 
      
  3. Para la consulta 1 , inserte ai. 
     No insertaremos ai en el trie, sino XOR(ai, x). Razón: 
     • Supongamos que insertamos a1, a2, luego XOR con x1, luego insertamos a3, luego XOR con x2. 
        
     • Cuando consultamos el mínimo ahora, encontraremos el valor mínimo en: {XOR(a1, x1, x2), XOR(a2, x1, x2), XOR(a3, x1, x2)} 
       Pero a3 solo ha sido XOR- ed con x2 y no x1. 
        
     • Por lo tanto, es fundamental que en cada momento que insertemos un elemento ai en el trie, insertemos XOR(ai, x). Esto asegura que cuando calculemos el mínimo, cancelará los XOR anteriores. 
       Entonces, en nuestro ejemplo, nuestro trie contendrá 
       {a1, a2, XOR(a3, x1)}. 
        
     • Cuando consultamos el valor mínimo de XOR(x), encontraremos el mínimo usando el método anterior de {XOR(a1, x1, x2), XOR(a2, x1, x2), XOR(a3, x2)}, que es lo que queremos. Insertar XOR(ai, x) asegurará que hagamos lo que hagamos con la operación mínima, no hagamos ningún XOR innecesario en ningún ai. 
        

A continuación se muestra la implementación en C++ de este enfoque:
 

// C++ program to operate
// queries in a given set
#include <bits/stdc++.h>
using namespace std;
 
const int Maxbits = 30;
 
// Function for Query 1
void Insert(int x, int curx,
            int* sz, int trie[100][2])
{
    // XOR each element before
    // storing it in the trie.
    x = x ^ curx;
    int p = 0;
 
    // Storing xored element in the trie.
    for (int i = Maxbits - 1; i >= 0; i--)
    {
        if (!trie[p][x >> i & 1])
            trie[p][x >> i & 1] = (*sz)++;
 
        p = trie[p][x >> i & 1];
    }
}
 
// Function for Query 2
void XorQuery(int x, int* curx)
{
    // Simply xor-ing all the number which
    // was asked to xor with the set elements.
    (*curx) = (*curx) ^ x;
}
 
// Function for Query 3
void MinXor(int x, int trie[100][2])
{
    int ans = 0, p = 0;
 
    // Finding the minimum element by checking
    // if x[i] bit is same with trie element.
    for (int i = Maxbits - 1; i >= 0; i--)
    {
        bool Currbit = (x >> i & 1);
 
        if (trie[p][Currbit])
            p = trie[p][Currbit];
 
        else {
            p = trie[p][!Currbit];
            ans |= 1 << i;
        }
    }
 
    cout << ans << endl;
}
 
// Driver code
int main()
{
    int sz = 1;
    int curx = 0;
    int trie[100][2] = { 0 };
 
    // Initialising the trie
    Insert(0, 0, &sz, trie);
 
    // Calling the Query
    MinXor(curx, trie);
    Insert(7, curx, &sz, trie);
    MinXor(curx, trie);
    XorQuery(4, &curx);
    XorQuery(8, &curx);
    XorQuery(3, &curx);
    Insert(10, curx, &sz, trie);
    Insert(3, curx, &sz, trie);
    MinXor(curx, trie);
    XorQuery(1, &curx);
 
    return 0;
}

# Python3 program to operate
# queries in a given set
 
Maxbits = 30
 
# Function for Query 1
 
 
def Insert(x, curx, trie):
    global sz
    # XOR each element before
    # storing it in the trie.
    x = x ^ curx
    p = 0
 
    # Storing xored element in the trie.
    for i in range(Maxbits - 1, -1, -1):
        if not(trie[p][x >> i & 1]):
            trie[p][x >> i & 1] = sz
            sz += 1
 
        p = trie[p][x >> i & 1]
 
 
# Function for Query 2
def XorQuery(x,):
    global curx
    # Simply xor-ing all the number which
    # was asked to xor with the set elements.
    curx ^= x
 
 
# Function for Query 3
def MinXor(x, trie):
    ans = 0
    p = 0
 
    # Finding the minimum element by checking
    # if x[i] bit is same with trie element.
    for i in range(Maxbits - 1, -1, -1):
        Currbit = (x >> i & 1)
 
        if (trie[p][Currbit]):
            p = trie[p][Currbit]
 
        else:
            p = trie[p][~Currbit]
            ans |= 1 << i
 
    print(ans)
 
 
# Driver code
if __name__ == '__main__':
    sz = 1
    curx = 0
    trie = [[0]*2 for _ in range(100)]
 
    # Initialising the trie
    Insert(0, 0, trie)
 
    # Calling the Query
    MinXor(curx, trie)
    Insert(7, curx, trie)
    MinXor(curx, trie)
    XorQuery(4, )
    XorQuery(8, )
    XorQuery(3, )
    Insert(10, curx, trie)
    Insert(3, curx,  trie)
    MinXor(curx, trie)
    XorQuery(1,)

0
0
3

Complejidad de tiempo:  O(N) por consulta. Donde N es el número de bits en el elemento de consulta.
Espacio Auxiliar: O(N)