Dada una array arr[] que consta de N enteros positivos y una array de consultas Q[] de tipo [L, R] , la tarea es encontrar el OR bit a bit del AND bit a bit de todos los posibles subarreglos no vacíos de la array después de actualizar el elemento de array en el índice L a R para cada consulta.
Ejemplos:
Entrada: arr[ ] = {1, 2, 3}, Q[ ] = {{1, 4}, {3, 0}} Salida: 7 6
Explicación :
Todos
los subarreglos son {1}, {2}, {3 }, {1, 2}, {2, 3} y {1, 2, 3}
Para la consulta 1: Actualizar arr[1] = 4, entonces la nueva array es {4, 2, 3}. El & bit a bit de todos los subarreglos es 4, 2, 3, 0, 2, 0 y el OR bit a bit ({4, 2, 3, 0, 2, 0}) es igual a 7. Para la consulta 2: Actualizar arr[3
] = 0, entonces la nueva array es {4, 2, 0}. El & bit a bit de todos los subarreglos es 4, 2, 0, 0, 0, 0 y el OR bit a bit ({4, 2, 0, 0, 0, 0}) es igual a 6.Entrada: arr[ ] = {1, 2, 1}, Q[ ] = {{2, 1}}
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array Q[] y, para cada consulta, actualizar el elemento de la array arr[L] a R y buscar todas las subarreglas y su AND bit a bit y almacenarlas en la nueva array. Después de almacenar el AND bit a bit, encuentre el OR bit a bit de la nueva array formada.
Complejidad de Tiempo: O(N 2 Q)
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el hecho de que el OR bit a bit del AND bit a bit resultante de todos los subarreglos generados es el mismo que el OR bit a bit resultante de todos los elementos presentes en el arreglo .
Por lo tanto, la idea es realizar las consultas e imprimir el valor de Bitwise OR de todos los elementos de la array después de actualizar la array cada vez.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the Bitwise OR
// of Bitwise AND of all possible
// subarrays after performing the
// every query
void performQuery(vector<int> arr,
vector<vector<int>> Q)
{
// Traversing each pair
// of the query
for (int i = 0; i < Q.size(); i++) {
// Stores the Bitwise OR
int or1 = 0;
// Updating the array
int x = Q[i][0];
arr[x - 1] = Q[i][1];
// Find the Bitwise OR of
// new updated array
for (int j = 0; j < arr.size(); j++) {
or1 = or1 | arr[j];
}
// Print the ans
cout<<or1<<" ";
}
}
// Driver Code
int main()
{
vector<int> arr({ 1, 2, 3 });
vector<int> v1({1,4});
vector<int> v2({3,0});
vector<vector<int>> Q;
Q.push_back(v1);
Q.push_back(v2);
performQuery(arr, Q);
}
// This code is contributed by ipg2016107.
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the Bitwise OR
// of Bitwise AND of all possible
// subarrays after performing the
// every query
static void performQuery(int arr[],
int Q[][])
{
// Traversing each pair
// of the query
for (int i = 0; i < Q.length; i++) {
// Stores the Bitwise OR
int or = 0;
// Updating the array
int x = Q[i][0];
arr[x - 1] = Q[i][1];
// Find the Bitwise OR of
// new updated array
for (int j = 0; j < arr.length; j++) {
or = or | arr[j];
}
// Print the ans
System.out.print(or + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3 };
int Q[][] = { { 1, 4 }, { 3, 0 } };
performQuery(arr, Q);
}
}
Python3
# Python program for the above approach # Function to find the Bitwise OR # of Bitwise AND of all possible # subarrays after performing the # every query def performQuery(arr, Q): # Traversing each pair # of the query for i in range (0, len(Q)): # Stores the Bitwise OR orr = 0 # Updating the array x = Q[i][0] arr[x - 1] = Q[i][1] # Find the Bitwise OR of # new updated array for j in range(0,len(arr)): orr = orr | arr[j] # Print the ans print(orr ,end= " ") # Driver Code arr = [1, 2, 3] Q = [[1, 4] , [3, 0]] performQuery(arr, Q) # This code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the Bitwise OR
// of Bitwise AND of all possible
// subarrays after performing the
// every query
static void performQuery(int []arr, int [,]Q)
{
// Traversing each pair
// of the query
for (int i = 0; i < Q.Length; i++) {
// Stores the Bitwise OR
int or = 0;
// Updating the array
int x = Q[i,0];
arr[x - 1] = Q[i,1];
// Find the Bitwise OR of
// new updated array
for (int j = 0; j < arr.Length; j++) {
or = or | arr[j];
}
// Print the ans
Console.Write(or + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3 };
int [,]Q = { { 1, 4 }, { 3, 0 } };
performQuery(arr, Q);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the Bitwise OR
// of Bitwise AND of all possible
// subarrays after performing the
// every query
function performQuery(arr, Q)
{
// Traversing each pair
// of the query
for (let i = 0; i < Q.length; i++) {
// Stores the Bitwise OR
let or = 0;
// Updating the array
let x = Q[i][0];
arr[x - 1] = Q[i][1];
// Find the Bitwise OR of
// new updated array
for (let j = 0; j < arr.length; j++) {
or = or | arr[j];
}
// Print the ans
document.write(or + " ");
}
}
// Driver Code
let arr = [1, 2, 3];
let Q = [[1, 4], [3, 0]];
performQuery(arr, Q);
// This code is contributed by Potta Lokesh
</script>
7 6
Complejidad temporal: O(N*Q)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rajatdubey179 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA