Dada una array arr[] y consultas Q , la tarea es encontrar la array actualizada resultante después de las consultas Q. Hay dos tipos de consultas y la siguiente operación es realizada por ellos:
- Actualizar (L, R, K): realice XOR para cada elemento dentro del rango L a R con K.
- Display(): muestra el estado actual de la array dada.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6}, Q = 2
Consulta 1: Actualizar (1, 5, 3)
Consulta 2: Mostrar()
Salida: 2 1 0 7 6 6
Explicación:
La consulta de actualización realiza XOR de todos los elementos en el rango [1, 5].
Después de realizar la consulta de actualización, la array anterior se muestra para la consulta de visualización porque:
1 ^ 3 = 2
2 ^ 3 = 1
3 ^ 3 = 0
4 ^ 3 = 7
5 ^ 3 = 6
Entrada: arr[] = {2, 4, 6, 8, 10}, Q = 3
Consulta 1: Actualizar (1, 3, 2)
Consulta 2: Actualizar (2, 4, 3)
Consulta 3: Mostrar()
Salida: 0 5 7 11 10
Explicación:
Hay son dos consultas de actualización.
Después de realizar la primera consulta de actualización, la array dada se cambia a {0, 6, 4, 8, 10}. Esto se debe a que:
2 ^ 2 = 0
4 ^ 2 = 6
6 ^ 2 = 4
Después de obtener esta array, esta array se cambia aún más para la segunda consulta como {0, 5, 7, 11, 10}. Esto se debe a que:
6 ^ 3 = 5
4 ^ 3 = 7
8 ^ 3 = 11
Enfoque ingenuo: el enfoque ingenuo para este problema es para cada consulta de actualización, ejecutar un ciclo de L a R y realizar la operación XOR con la K dada con todos los elementos de arr[L] a arr[R]. Para realizar la consulta de visualización, simplemente imprima la array arr[]. La complejidad temporal de este enfoque es O(NQ), donde N es la longitud de la array y Q es el número de consultas.
Enfoque eficiente: la idea es utilizar un algoritmo de kadane para este problema.
- Se define una array vacía res[] con la misma longitud que la array original.
- Para cada consulta de actualización {L, R, K}, la array res[] se modifica como:
- XOR K a res[L]
- XOR K a res[R + 1]
- Cada vez que el usuario realiza una consulta de visualización:
- Inicialice una variable de contador ‘i’ en el índice 1.
- Realiza la operación:
res[i] = res[i] ^ res[i - 1]
- Inicialice una variable de contador ‘i’ en el índice 0.
- Para cada índice en la array, la respuesta requerida es:
arr[i] ^ res[i]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to perform the // XOR range updates on an array #include <bits/stdc++.h> using namespace std; // Function to perform the update operation // on the given array void update(int res[], int L, int R, int K) { // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the starting // index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending index // in the given [L, R]. res[R + 1] ^= K; } // Function to display the resulting array void display(int arr[], int res[], int n) { for (int i = 1; i < n; i++) { // Finding the resultant value in the // result array res[i] = res[i] ^ res[i - 1]; } for (int i = 0; i < n; i++) { // Combining the effects of the updates // with the original array without // changing the initial array. cout << (arr[i] ^ res[i]) << " "; } cout << endl; } // Driver code int main() { int arr[] = { 2, 4, 6, 8, 10 }; int N = sizeof(arr) / sizeof(arr[0]); int res[N]; memset(res, 0, sizeof(res)); // Query 1 int L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N); return 0; }
Java
// Java implementation to perform the // XOR range updates on an array class GFG{ // Function to perform the update // operation on the given array static void update(int res[], int L, int R, int K) { // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the // starting index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending // index in the given [L, R]. res[R + 1] ^= K; } // Function to display the resulting array static void display(int arr[], int res[], int n) { int i; for(i = 1; i < n; i++) { // Finding the resultant value // in the result array res[i] = res[i] ^ res[i - 1]; } for(i = 0; i < n; i++) { // Combining the effects of the // updates with the original array // without changing the initial array. System.out.print((arr[i] ^ res[i]) + " "); } System.out.println(); } // Driver code public static void main(String []args) { int arr[] = { 2, 4, 6, 8, 10 }; int N = arr.length; int res[] = new int[N]; // Query 1 int L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N); } } // This code is contributed by chitranayal
Python3
# Python3 implementation to perform the # XOR range updates on an array # Function to perform the update operation # on the given array def update(res, L, R, K): # Converting the indices to # 0 indexing. L = L - 1 R = R - 1 # Saving the XOR of K from the starting # index in the range [L, R]. res[L] = res[L] ^ K # Saving the XOR of K at the ending index # in the given [L, R]. res[R + 1] = res[R + 1] ^ K # Function to display the resulting array def display(arr, res, n): for i in range(1, n): # Finding the resultant value in the # result array res[i] = res[i] ^ res[i - 1] for i in range(0, n): # Combining the effects of the updates # with the original array without # changing the initial array. print (arr[i] ^ res[i], end = " ") # Driver code arr = [ 2, 4, 6, 8, 10 ] N = len(arr) res = [0] * N # Query 1 L = 1 R = 3 K = 2 update(res, L, R, K) # Query 2 L = 2 R = 4 K = 3 update(res, L, R, K) # Query 3 display(arr, res, N) # This code is contributed by Pratik Basu
C#
// C# implementation to perform the // XOR range updates on an array using System; class GFG{ // Function to perform the update // operation on the given array static void update(int []res, int L, int R, int K) { // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the // starting index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending // index in the given [L, R]. res[R + 1] ^= K; } // Function to display the resulting array static void display(int []arr, int []res, int n) { int i; for(i = 1; i < n; i++) { // Finding the resultant value // in the result array res[i] = res[i] ^ res[i - 1]; } for(i = 0; i < n; i++) { // Combining the effects of the // updates with the original array // without changing the initial array. Console.Write((arr[i] ^ res[i]) + " "); } Console.WriteLine(); } // Driver code public static void Main() { int []arr = { 2, 4, 6, 8, 10 }; int N = arr.Length; int []res = new int[N]; // Query 1 int L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N); } } // This code is contributed by Code_Mech
Javascript
<script> // Javascript implementation to perform the // XOR range updates on an array // Function to perform the update // operation on the given array function update(res, L, R, K) { // Converting the indices to // 0 indexing. L -= 1; R -= 1; // Saving the XOR of K from the // starting index in the range [L, R]. res[L] ^= K; // Saving the XOR of K at the ending // index in the given [L, R]. res[R + 1] ^= K; } // Function to display the resulting array function display(arr, res, n) { let i; for(i = 1; i < n; i++) { // Finding the resultant value // in the result array res[i] = res[i] ^ res[i - 1]; } for(i = 0; i < n; i++) { // Combining the effects of the // updates with the original array // without changing the initial array. document.write((arr[i] ^ res[i]) + " "); } document.write( "<br/>"); } // Driver Code let arr = [ 2, 4, 6, 8, 10 ]; let N = arr.length; let res = Array.from({length: N}, (_, i) => 0); // Query 1 let L = 1, R = 3, K = 2; update(res, L, R, K); // Query 2 L = 2; R = 4; K = 3; update(res, L, R, K); // Query 3 display(arr, res, N); </script>
0 5 7 11 10
Complejidad del tiempo:
- La complejidad de tiempo para la actualización es O(1) .
- La complejidad de tiempo para mostrar la array es O(N) .
Espacio Auxiliar: O(N)
Nota: este enfoque funciona muy bien cuando las consultas de actualización son muy altas en comparación con las consultas de visualización.