Encuentre la suma de la array usando Bitwise OR después de dividir la array dada en dos mitades después de K cambios circulares

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *