Dada una array A[] de longitud N , donde N es un número par, la tarea es responder Q consultas independientes donde cada consulta consiste en un número entero positivo K que representa el número de desplazamientos circulares realizados en la array y encontrar la suma de elementos realizando la operación Bitwise OR en la array dividida.
Nota: Cada consulta comienza con la array original.
Ejemplos:
Entrada: A[] = {12, 23, 4, 21, 22, 76}, Q = 1, K = 2
Salida: 117
Explicación:
Dado que K es 2, array modificada A[]={22, 76, 12, 23, 4, 21}.
OR bit a bit de la primera mitad del arreglo = (22 | 76 | 12) = 94
OR bit a bit de la segunda mitad del arreglo = (21 | 23 | 4) = 23 La
suma de los valores OR es 94 + 23 = 117
Entrada: A[] = {7, 44, 19, 86, 65, 39, 75, 101}, Q = 1, K = 4
Salida: 238
Dado que K es 4, array modificada A[]={65, 39, 75, 101, 7, 44, 19, 86}.
OR bit a bit de la primera mitad del arreglo = 111
OR bit a bit de la segunda mitad del arreglo = 127
La suma de los valores OR es 111 + 127 = 238
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, el enfoque más simple es desplazar cada elemento de la array en K % (N / 2) y luego atravesar la array para calcular el OR de las dos mitades para cada consulta. Pero este método no es eficiente y, por lo tanto, puede optimizarse aún más.
Enfoque eficiente:
para optimizar el enfoque mencionado anteriormente, podemos tomar la ayuda de la estructura de datos del árbol de segmentos .
Observación:
- Podemos observar que después de exactamente N / 2 desplazamientos circulares a la derecha, las dos mitades de la array se vuelven iguales a las de la array original. Esto reduce efectivamente el número de rotaciones a K % (N / 2) .
- Realizar un desplazamiento circular a la derecha consiste básicamente en desplazar el último elemento de la array hacia el frente. Entonces, para cualquier número entero positivo X , realizar X desplazamientos circulares a la derecha es igual a desplazar los últimos X elementos de la array al frente.
Los siguientes son los pasos para resolver el problema:
- Construya un árbol de segmentos para la array original A[] y asigne una variable, digamos i = K % (N / 2) .
- Luego, para cada consulta, usamos el árbol de segmentos de encontrar el OR bit a bit; es decir OR bit a bit de i elementos del final OR bit a bit OR del primero (N / 2) – i – 1 elementos.
- Luego calcule el OR bit a bit de los elementos en el rango [(N / 2) – i, N – i – 1] .
- Sume los dos resultados para obtener la respuesta de la i-ésima consulta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find Bitwise OR of two
// equal halves of an array after performing
// K right circular shifts
#include <bits/stdc++.h>
const int MAX = 100005;
using namespace std;
// Array for storing
// the segment tree
int seg[4 * MAX];
// Function to build the segment tree
void build(int node, int l, int r, int a[])
{
if (l == r)
seg[node] = a[l];
else {
int mid = (l + r) / 2;
build(2 * node, l, mid, a);
build(2 * node + 1, mid + 1, r, a);
seg[node] = (seg[2 * node]
| seg[2 * node + 1]);
}
}
// Function to return the OR
// of elements in the range [l, r]
int query(int node, int l, int r,
int start, int end, int a[])
{
// Check for out of bound condition
if (l > end or r < start)
return 0;
if (start <= l and r <= end)
return seg[node];
// Find middle of the range
int mid = (l + r) / 2;
// Recurse for all the elements in array
return ((query(2 * node, l, mid,
start, end, a))
| (query(2 * node + 1, mid + 1,
r, start, end, a)));
}
// Function to find the OR sum
void orsum(int a[], int n, int q, int k[])
{
// Function to build the segment Tree
build(1, 0, n - 1, a);
// Loop to handle q queries
for (int j = 0; j < q; j++) {
// Effective number of
// right circular shifts
int i = k[j] % (n / 2);
// Calculating the OR of
// the two halves of the
// array from the segment tree
// OR of second half of the
// array [n/2-i, n-1-i]
int sec = query(1, 0, n - 1,
n / 2 - i, n - i - 1, a);
// OR of first half of the array
// [n-i, n-1]OR[0, n/2-1-i]
int first = (query(1, 0, n - 1, 0,
n / 2 - 1 - i, a)
| query(1, 0, n - 1,
n - i, n - 1, a));
int temp = sec + first;
// Print final answer to the query
cout << temp << endl;
}
}
// Driver Code
int main()
{
int a[] = { 7, 44, 19, 86, 65, 39, 75, 101 };
int n = sizeof(a) / sizeof(a[0]);
int q = 2;
int k[q] = { 4, 2 };
orsum(a, n, q, k);
return 0;
}
Java
// Java program to find Bitwise OR of two
// equal halves of an array after performing
// K right circular shifts
import java.util.*;
class GFG{
static int MAX = 100005;
// Array for storing
// the segment tree
static int []seg = new int[4 * MAX];
// Function to build the segment tree
static void build(int node, int l,
int r, int a[])
{
if (l == r)
seg[node] = a[l];
else
{
int mid = (l + r) / 2;
build(2 * node, l, mid, a);
build(2 * node + 1, mid + 1, r, a);
seg[node] = (seg[2 * node] |
seg[2 * node + 1]);
}
}
// Function to return the OR
// of elements in the range [l, r]
static int query(int node, int l, int r,
int start, int end, int a[])
{
// Check for out of bound condition
if (l > end || r < start)
return 0;
if (start <= l && r <= end)
return seg[node];
// Find middle of the range
int mid = (l + r) / 2;
// Recurse for all the elements in array
return ((query(2 * node, l, mid,
start, end, a)) |
(query(2 * node + 1, mid + 1,
r, start, end, a)));
}
// Function to find the OR sum
static void orsum(int a[], int n,
int q, int k[])
{
// Function to build the segment Tree
build(1, 0, n - 1, a);
// Loop to handle q queries
for(int j = 0; j < q; j++)
{
// Effective number of
// right circular shifts
int i = k[j] % (n / 2);
// Calculating the OR of
// the two halves of the
// array from the segment tree
// OR of second half of the
// array [n/2-i, n-1-i]
int sec = query(1, 0, n - 1,
n / 2 - i,
n - i - 1, a);
// OR of first half of the array
// [n-i, n-1]OR[0, n/2-1-i]
int first = (query(1, 0, n - 1, 0,
n / 2 - 1 - i, a) |
query(1, 0, n - 1,
n - i, n - 1, a));
int temp = sec + first;
// Print final answer to the query
System.out.print(temp + "\n");
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 7, 44, 19, 86, 65, 39, 75, 101 };
int n = a.length;
int q = 2;
int k[] = { 4, 2 };
orsum(a, n, q, k);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find Bitwise OR of two # equal halves of an array after performing # K right circular shifts MAX = 100005 # Array for storing # the segment tree seg = [0] * (4 * MAX) # Function to build the segment tree def build(node, l, r, a): if (l == r): seg[node] = a[l] else: mid = (l + r) // 2 build(2 * node, l, mid, a) build(2 * node + 1, mid + 1, r, a) seg[node] = (seg[2 * node] | seg[2 * node + 1]) # Function to return the OR # of elements in the range [l, r] def query(node, l, r, start, end, a): # Check for out of bound condition if (l > end or r < start): return 0 if (start <= l and r <= end): return seg[node] # Find middle of the range mid = (l + r) // 2 # Recurse for all the elements in array return ((query(2 * node, l, mid, start, end, a)) | (query(2 * node + 1, mid + 1, r, start, end, a))) # Function to find the OR sum def orsum(a, n, q, k): # Function to build the segment Tree build(1, 0, n - 1, a) # Loop to handle q queries for j in range(q): # Effective number of # right circular shifts i = k[j] % (n // 2) # Calculating the OR of # the two halves of the # array from the segment tree # OR of second half of the # array [n/2-i, n-1-i] sec = query(1, 0, n - 1, n // 2 - i, n - i - 1, a) # OR of first half of the array # [n-i, n-1]OR[0, n/2-1-i] first = (query(1, 0, n - 1, 0, n // 2 - 1 - i, a) | query(1, 0, n - 1, n - i, n - 1, a)) temp = sec + first # Print final answer to the query print(temp) # Driver Code if __name__ == "__main__": a = [ 7, 44, 19, 86, 65, 39, 75, 101 ] n = len(a) q = 2 k = [ 4, 2 ] orsum(a, n, q, k) # This code is contributed by chitranayal
C#
// C# program to find Bitwise OR of two
// equal halves of an array after performing
// K right circular shifts
using System;
class GFG{
static int MAX = 100005;
// Array for storing
// the segment tree
static int []seg = new int[4 * MAX];
// Function to build the segment tree
static void build(int node, int l,
int r, int []a)
{
if (l == r)
seg[node] = a[l];
else
{
int mid = (l + r) / 2;
build(2 * node, l, mid, a);
build(2 * node + 1, mid + 1, r, a);
seg[node] = (seg[2 * node] |
seg[2 * node + 1]);
}
}
// Function to return the OR
// of elements in the range [l, r]
static int query(int node, int l, int r,
int start, int end, int []a)
{
// Check for out of bound condition
if (l > end || r < start)
return 0;
if (start <= l && r <= end)
return seg[node];
// Find middle of the range
int mid = (l + r) / 2;
// Recurse for all the elements in array
return ((query(2 * node, l, mid,
start, end, a)) |
(query(2 * node + 1, mid + 1,
r, start, end, a)));
}
// Function to find the OR sum
static void orsum(int []a, int n,
int q, int []k)
{
// Function to build the segment Tree
build(1, 0, n - 1, a);
// Loop to handle q queries
for(int j = 0; j < q; j++)
{
// Effective number of
// right circular shifts
int i = k[j] % (n / 2);
// Calculating the OR of
// the two halves of the
// array from the segment tree
// OR of second half of the
// array [n/2-i, n-1-i]
int sec = query(1, 0, n - 1,
n / 2 - i,
n - i - 1, a);
// OR of first half of the array
// [n-i, n-1]OR[0, n/2-1-i]
int first = (query(1, 0, n - 1, 0,
n / 2 - 1 - i, a) |
query(1, 0, n - 1,
n - i, n - 1, a));
int temp = sec + first;
// Print readonly answer to the query
Console.Write(temp + "\n");
}
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 7, 44, 19, 86, 65, 39, 75, 101 };
int n = a.Length;
int q = 2;
int []k = { 4, 2 };
orsum(a, n, q, k);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to find Bitwise OR of two
// equal halves of an array after performing
// K right circular shifts
const MAX = 100005;
// Array for storing
// the segment tree
var seg = Array(4 * MAX).fill(0);
// Function to build the segment tree
function build(node , l , r , a) {
if (l == r)
seg[node] = a[l];
else {
var mid = parseInt((l + r) / 2);
build(2 * node, l, mid, a);
build(2 * node + 1, mid + 1, r, a);
seg[node] = (seg[2 * node] | seg[2 * node + 1]);
}
}
// Function to return the OR
// of elements in the range [l, r]
function query(node , l , r , start , end , a) {
// Check for out of bound condition
if (l > end || r < start)
return 0;
if (start <= l && r <= end)
return seg[node];
// Find middle of the range
var mid = parseInt((l + r) / 2);
// Recurse for all the elements in array
return ((query(2 * node, l, mid, start, end, a)) | (query(2 * node + 1, mid + 1, r, start, end, a)));
}
// Function to find the OR sum
function orsum(a , n , q , k) {
// Function to build the segment Tree
build(1, 0, n - 1, a);
// Loop to handle q queries
for (j = 0; j < q; j++) {
// Effective number of
// right circular shifts
var i = k[j] % (n / 2);
// Calculating the OR of
// the two halves of the
// array from the segment tree
// OR of second half of the
// array [n/2-i, n-1-i]
var sec = query(1, 0, n - 1, n / 2 - i, n - i - 1, a);
// OR of first half of the array
// [n-i, n-1]OR[0, n/2-1-i]
var first = (query(1, 0, n - 1, 0, n / 2 - 1 - i, a) | query(1, 0, n - 1, n - i, n - 1, a));
var temp = sec + first;
// Print final answer to the query
document.write(temp + "<br/>");
}
}
// Driver Code
var a = [ 7, 44, 19, 86, 65, 39, 75, 101 ];
var n = a.length;
var q = 2;
var k = [ 4, 2 ];
orsum(a, n, q, k);
// This code is contributed by Rajput-Ji.
</script>
Producción:
238 230
Complejidad de tiempo: O(N + Q*log(N))
Espacio auxiliar: O(4*MAX)
Publicación traducida automáticamente
Artículo escrito por nishitsharma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA