Recuento de subarreglos en el rango [L, R] que tienen XOR + 1 igual a XOR (XOR) 1 para M consultas

Dada una array, arr[] de N enteros positivos y M consultas que constan de dos enteros [L i , R i ] donde  1 ≤ Li ≤ Ri ≤ N . Para cada consulta, encuentre el número de subarreglos en el rango [L i , R i ] para los cuales (X+1)=(X⊕1) donde X denota el xor de un subarreglo.

Entrada: arr[]= {1, 2, 9, 8, 7}, queries[] = {{1, 5}, {3, 4}}
Salida: 6 1
Explicación: 
Consulta 1: L=1, R= 5: subarreglos [1, 3], [1, 4], [2, 2], [2, 5], [3, 5], [4, 4]
Consulta 2: L=3, R=4: subarreglo [4, 4]

Entrada: arr[] = {1, 2, 2, 4, 5}, consultas[] = {{2, 4}, {3, 5}}
Salida: 6 3

Enfoque ingenuo: para cada consulta, seleccione el rango dado [L i , R i ] y para cada subarreglo verifique si satisface la condición dada. 
Complejidad del tiempo: O(N 3 * M)

Enfoque eficiente: En el problema anterior, se pueden hacer las siguientes observaciones:

  • Para satisfacer la condición dada, X debe ser un número par porque
    • Si X es par,   ( X ⊕1)=( X +1)
    • Si X es impar,   ( X ⊕1)=( X −1)
  • Para un subarreglo, su xor será par si el conteo de números impares en ese subarreglo es par.
  • Si el conteo de números impares es par, entonces la suma del subarreglo será par. Entonces, los subarreglos con una suma par son la respuesta a este problema.

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;
 
vector<int> countXorSubarr(
    vector<int> arr,
    vector<vector<int> > queries,
    int n, int m)
{
 
    // As queries are in 1-based indexing,
    // add one dummy entry in beginning
    // of arr to make it 1-indexed
    arr.insert(arr.begin(), 0);
 
    // sum[] will contain parity
    // of prefix sum till index i
    // count[] will contain
    // number of 0s in sum[]
    int count[n + 1], sum[n + 1];
    count[0] = sum[0] = 0;
 
    for (int i = 1; i <= n; i++) {
 
        // Take the parity of current sum
        sum[i] = (sum[i - 1] + arr[i]) % 2;
        count[i] = count[i - 1];
 
        // If current parity is even,
        // increase the count
        if (sum[i] % 2 == 0)
            count[i]++;
    }
 
    // Array to hold the answer of 'm' queries
    vector<int> ans;
 
    // Iterate through queries and use handshake
    // lemma to count even sum subarrays
    // ( Note that an even sum can
    // be formed by two even or two odd )
    for (vector<int> qu : queries) {
        int L = qu[0], R = qu[1];
 
        // Find count of even and
        // odd sums in range [L, R]
        int even = count[R] - count[L - 1];
        int odd = (R - L + 1) - even;
 
        // If prefix sum at L-1 is odd,
        // then we need to swap
        // our counts of odd and even
        if (sum[L - 1] == 1)
            swap(even, odd);
 
        // Taking no element is also
        // considered an even sum
        // so even will be increased by 1
        // (This is the condition when
        // a prefix of even sum is taken)
        even++;
 
        // Find number of ways to
        // select two even's or two odd's
        int subCount = (even * (even - 1)) / 2
                       + (odd * (odd - 1)) / 2;
 
        ans.push_back(subCount);
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int n = 5;
    vector<int> arr = { 1, 2, 9, 8, 7 };
    int m = 2;
    vector<vector<int> > queries
        = { { 1, 5 }, { 3, 4 } };
 
    // Function call and print answer
    vector<int> ans
        = countXorSubarr(arr, queries, n, m);
    for (int x : ans)
        cout << x << " ";
    cout << endl;
 
    return 0;
}

Java

// Java program for the above approach
import java.util.ArrayList;
 
class GFG
{
 
    public static ArrayList<Integer> countXorSubarr(int[] arr, int[][] queries, int n, int m) {
 
        // As queries are in 1-based indexing,
        // add one dummy entry in beggining
        // of arr to make it 1-indexed
        // arr.insert(arr.begin(), 0);
        int[] temp_arr = new int[arr.length + 1];
        temp_arr[0] = 0;
        for (int i = 1; i < temp_arr.length; i++) {
            temp_arr[i] = arr[i - 1];
        }
        arr = temp_arr.clone();
 
        // sum[] will contain parity
        // of prefix sum till index i
        // count[] will contain
        // number of 0s in sum[]
        int[] count = new int[n + 1];
        int[] sum = new int[n + 1];
        count[0] = sum[0] = 0;
 
        for (int i = 1; i <= n; i++) {
 
            // Take the parity of current sum
            sum[i] = (sum[i - 1] + arr[i]) % 2;
            count[i] = count[i - 1];
 
            // If current parity is even,
            // increase the count
            if (sum[i] % 2 == 0)
                count[i]++;
        }
 
        // Array to hold the answer of 'm' queries
        ArrayList<Integer> ans = new ArrayList<Integer>();
 
        // Iterate through queries and use handshake
        // lemma to count even sum subarrays
        // ( Note that an even sum can
        // be formed by two even or two odd )
        for (int[] qu : queries) {
            int L = qu[0], R = qu[1];
 
            // Find count of even and
            // odd sums in range [L, R]
            int even = count[R] - count[L - 1];
            int odd = (R - L + 1) - even;
 
            // If prefix sum at L-1 is odd,
            // then we need to swap
            // our counts of odd and even
            if (sum[L - 1] == 1) {
                int temp = even;
                even = odd;
                odd = temp;
            }
 
            // Taking no element is also
            // considered an even sum
            // so even will be increased by 1
            // (This is the condition when
            // a prefix of even sum is taken)
            even++;
 
            // Find number of ways to
            // select two even's or two odd's
            int subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2;
 
            ans.add(subCount);
        }
 
        return ans;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 5;
        int[] arr = { 1, 2, 9, 8, 7 };
        int m = 2;
        int[][] queries = { { 1, 5 }, { 3, 4 } };
 
        // Function call and print answer
        ArrayList<Integer> ans = countXorSubarr(arr, queries, n, m);
        for (int x : ans)
            System.out.print(x + " ");
        System.out.println("");
 
    }
}
 
// This code is contributed by saurabh_jaiswal.

Python3

# python program for the above approach
import math
def countXorSubarr(arr, queries, n, m):
 
        # As queries are in 1-based indexing,
        # add one dummy entry in beggining
        # of arr to make it 1-indexed
    arr.insert(0, 0)
 
    # sum[] will contain parity
    # of prefix sum till index i
    # count[] will contain
    # number of 0s in sum[]
    count = [0 for _ in range(n + 1)]
    sum = [0 for _ in range(n + 1)]
 
    for i in range(1, n+1):
 
                # Take the parity of current sum
        sum[i] = (sum[i - 1] + arr[i]) % 2
        count[i] = count[i - 1]
 
        # If current parity is even,
        # increase the count
        if (sum[i] % 2 == 0):
            count[i] += 1
 
        # Array to hold the answer of 'm' queries
    ans = []
 
    # Iterate through queries and use handshake
    # lemma to count even sum subarrays
    # ( Note that an even sum can
    # be formed by two even or two odd )
    for qu in queries:
 
        L = qu[0]
        R = qu[1]
 
        # Find count of even and
        # odd sums in range [L, R]
        even = count[R] - count[L - 1]
        odd = (R - L + 1) - even
 
        # If prefix sum at L-1 is odd,
        # then we need to swap
        # our counts of odd and even
        if (sum[L - 1] == 1):
            temp = even
            even = odd
            odd = temp
 
            # Taking no element is also
            # considered an even sum
            # so even will be increased by 1
            # (This is the condition when
            # a prefix of even sum is taken)
        even += 1
 
        # Find number of ways to
        # select two even's or two odd's
        subCount = (even * (even - 1)) // 2 + (odd * (odd - 1)) // 2
        ans.append(subCount)
    return ans
 
# Driver code
if __name__ == "__main__":
 
    n = 5
    arr = [1, 2, 9, 8, 7]
    m = 2
    queries = [[1, 5], [3, 4]]
 
    # Function call and print answer
    ans = countXorSubarr(arr, queries, n, m)
    for x in ans:
        print(x, end=" ")
 
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
    public static List<int> countXorSubarr(int[] arr, int[,] queries, int n, int m)
    {
 
        // As queries are in 1-based indexing,
        // add one dummy entry in beggining
        // of arr to make it 1-indexed
        // arr.insert(arr.begin(), 0);
        int[] temp_arr = new int[arr.Length + 1];
        temp_arr[0] = 0;
        for (int i = 1; i < temp_arr.Length; i++) {
            temp_arr[i] = arr[i - 1];
        }
        arr = temp_arr;
 
        // sum[] will contain parity
        // of prefix sum till index i
        // []count will contain
        // number of 0s in sum[]
        int[] count = new int[n + 1];
        int[] sum = new int[n + 1];
        count[0] = sum[0] = 0;
 
        for (int i = 1; i <= n; i++) {
 
            // Take the parity of current sum
            sum[i] = (sum[i - 1] + arr[i]) % 2;
            count[i] = count[i - 1];
 
            // If current parity is even,
            // increase the count
            if (sum[i] % 2 == 0)
                count[i]++;
        }
 
        // Array to hold the answer of 'm' queries
        List<int> ans = new List<int>();
 
        // Iterate through queries and use handshake
        // lemma to count even sum subarrays
        // ( Note that an even sum can
        // be formed by two even or two odd )
         
        for(int i = 0; i < queries.GetLength(0); i++)
        {
            int L = queries[i,0], R = queries[i,1];
 
            // Find count of even and
            // odd sums in range [L, R]
            int even = count[R] - count[L - 1];
            int odd = (R - L + 1) - even;
 
            // If prefix sum at L-1 is odd,
            // then we need to swap
            // our counts of odd and even
            if (sum[L - 1] == 1) {
                int temp = even;
                even = odd;
                odd = temp;
            }
 
            // Taking no element is also
            // considered an even sum
            // so even will be increased by 1
            // (This is the condition when
            // a prefix of even sum is taken)
            even++;
 
            // Find number of ways to
            // select two even's or two odd's
            int subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2;
 
            ans.Add(subCount);
         
        }
        return ans;
    }
      public static int[] GetRow(int[,] matrix, int row)
      {
        var rowLength = matrix.GetLength(1);
        var rowVector = new int[rowLength];
 
        for (var i = 0; i < rowLength; i++)
          rowVector[i] = matrix[row, i];
 
        return rowVector;
      }
   
    // Driver code
    public static void Main(String []args)
    {
        int n = 5;
        int[] arr = { 1, 2, 9, 8, 7 };
        int m = 2;
        int[,] queries = { { 1, 5 }, { 3, 4 } };
 
        // Function call and print answer
        List<int> ans = countXorSubarr(arr, queries, n, m);
        foreach (int x in ans)
            Console.Write(x + " ");
        Console.WriteLine("");
 
    }
}
 
// This code contributed by shikhasingrajput

Javascript

<script>
       // JavaScript Program to implement
       // the above approach
       function countXorSubarr(arr, queries, n, m)
       {
 
           // sum[] will contain parity
           // of prefix sum till index i
           // count[] will contain
           // number of 0s in sum[]
           let count = new Array(n + 1), sum = new Array(n + 1);
           count[0] = sum[0] = 0;
 
           for (let i = 1; i <= n; i++) {
 
               // Take the parity of current sum
               sum[i] = (sum[i - 1] + arr[i - 1]) % 2;
               count[i] = count[i - 1];
 
               // If current parity is even,
               // increase the count
               if (sum[i] % 2 == 0)
                   count[i]++;
           }
 
           // Array to hold the answer of 'm' queries
           let ans = [];
 
           // Iterate through queries and use handshake
           // lemma to count even sum subarrays
           // ( Note that an even sum can
           // be formed by two even or two odd )
           for (let qu of queries) {
               let L = qu[0], R = qu[1];
 
               // Find count of even and
               // odd sums in range [L, R]
               let even = count[R] - count[L - 1];
               let odd = (R - L + 1) - even;
 
               // If prefix sum at L-1 is odd,
               // then we need to swap
               // our counts of odd and even
               if (sum[L - 1] == 1) {
                   temp = even
                   even = odd
                   odd = temp
               }
 
               // Taking no element is also
               // considered an even sum
               // so even will be increased by 1
               // (This is the condition when
               // a prefix of even sum is taken)
               even++;
 
               // Find number of ways to
               // select two even's or two odd's
               let subCount = (even * (even - 1)) / 2
                   + (odd * (odd - 1)) / 2;
 
               ans.push(subCount);
           }
 
           return ans;
       }
 
       // Driver code
       let n = 5;
       let arr = [1, 2, 9, 8, 7];
       let m = 2;
       let queries
           = [[1, 5], [3, 4]];
 
       // Function call and print answer
       let ans
           = countXorSubarr(arr, queries, n, m);
       for (let x of ans)
           document.write(x + " ");
 
   // This code is contributed by Potta Lokesh
   </script>
Producción

6 1 

Complejidad temporal: O(N+M)
Espacio auxiliar: O(N+M)

Publicación traducida automáticamente

Artículo escrito por himanshu77 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 *