Consultas para reemplazar cada elemento de la array por su XOR con un valor dado con actualizaciones

Dada una array, que inicialmente consta de 0 como único elemento presente y operaciones Q de los dos tipos siguientes:

• Agregar (X): inserta X en la array.
• Actualización (X): reemplace cada elemento de array A _i por A _i ^ X , donde ^ es la operación XOR .

Ejemplos:

Entrada: Q = 2
Añadir(5)
Actualizar(2)
Salida: 2 7
Explicación:
Inicialmente, Array = {0}
Consulta 1: Array = {0, 5}
Consulta 2: Array = {0^2, 5^2} => {2, 7}

Entrada: Q = 2
Sumar(3)
Sumar(5)
Salida: 0 3 5 

Enfoque: la idea es almacenar una variable que almacene el valor que se va a aplicar XOR con cada elemento del arreglo y, en el momento de la inserción del elemento en el arreglo, para eliminar el efecto del valor XOR, aplicar la operación XOR . consigo mismo Siga los pasos a continuación para resolver el problema:

• Mantenga una variable, digamos efecto , para almacenar el valor XOR final.
• Para la operación Agregar (X): agregue X al final de la lista y actualice su valor con el efecto X ^ .
• Para Operation Update(X): actualice el valor de ‘ efecto’ con efecto ^ X. Esto es para obtener un efecto XOR actualizado hasta ahora.
• Después de completar todas las operaciones anteriores, actualice todos los elementos de la array con su XOR con efecto , es decir, para todos los A _i , actualice A _i = A _i ^ efecto .

A continuación se muestra la implementación del enfoque anterior:

// C++ program of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
// Function to insert an element
// into the array
void add(vector<int>& arr, int x)
{
    arr.push_back(x);
}
 
// Function to update every array
// element a[i] by a[i] ^ x
void update(int& effect, int x)
{
    effect = effect ^ x;
}
 
// Function to compute the final
// results after the operations
void computeResults(vector<int>& arr,
                    int effect)
{
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = arr[i] ^ effect;
        cout << arr[i] << " ";
    }
}
 
// Driver Code
signed main()
{
    vector<int> arr = { 0 };
    int effect = 0;
 
    // Queries
    add(arr, 5);
    update(effect, 2);
 
    // Function Call
    computeResults(arr, effect);
}

// Java program of
// the above approach
import java.util.*;
class GFG{
   
static Vector<Integer> arr =
              new Vector<Integer>();
static int effect;
   
// Function to insert an element
// into the array
static void add(int x)
{
  arr.add(x);
}
 
// Function to update every array
// element a[i] by a[i] ^ x
static void update(int x)
{
  effect = effect ^ x;
}
 
// Function to compute the final
// results after the operations
static void computeResults()
{
  for (int i = 0; i < arr.size(); i++)
  {
    arr.set(i, arr.get(i) ^ effect);
    System.out.print(arr.get(i) + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
  arr = new Vector<Integer>();
  arr.add(0);
  effect = 0;
 
  // Queries
  add(5);
  update(2);
 
  // Function Call
  computeResults();
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program of the above approach
 
# Function to insert an element
# into the array
def add(arr, x):
     
    arr.append(x)
 
# Function to update every array
# element a[i] by a[i] ^ x
def update(effect, x):
 
    effect = effect ^ x
    return effect
 
# Function to compute the final
# results after the operations
def computeResults(arr, effect):
 
    for i in range(len(arr)):
        arr[i] = arr[i] ^ effect
        print(arr[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
 
    arr = [0]
    effect = 0
 
    # Queries
    add(arr, 5)
    effect = update(effect, 2)
 
    # Function call
    computeResults(arr, effect)
 
# This code is contributed by mohit kumar 29

// C# program of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
   
static List<int> arr = new List<int>();
static int effect;
   
// Function to insert an element
// into the array
static void add(int x)
{
  arr.Add(x);
}
 
// Function to update every array
// element a[i] by a[i] ^ x
static void update(int x)
{
  effect = effect ^ x;
}
 
// Function to compute the final
// results after the operations
static void computeResults()
{
  for (int i = 0; i < arr.Count; i++)
  {
    arr[i] = arr[i] ^ effect;
    Console.Write(arr[i] + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  arr = new List<int>();
  arr.Add(0);
  effect = 0;
 
  // Queries
  add(5);
  update(2);
 
  // Function Call
  computeResults();
}
}
 
// This code is contributed by shikhasingrajput

<script>
// Javascript program of the above approach
 
// Function to insert an element
// into the array
function add(arr, x)
{
    arr.push(x);
}
 
// Function to update every array
// element a[i] by a[i] ^ x
function update(effect, x)
{
    effect = effect ^ x;
    return effect;
}
 
// Function to compute the final
// results after the operations
function computeResults(arr, effect) {
    for (let i = 0; i < arr.length; i++) {
        arr[i] = arr[i] ^ effect;
        document.write(arr[i] + " ");
    }
}
 
// Driver Code
let arr = [0];
let effect = 0;
 
// Queries
add(arr, 5);
effect = update(effect, 2)
 
// Function Call
computeResults(arr, effect);
 
// This code is contributed by gfgking.
</script>

2 7

Tiempo Complejidad: O(Q) 
Espacio Auxiliar: O(1)