Recuento de tripletes cuyo XOR incluso ha establecido bits en el rango [L, R] para consultas Q

Dada una array arr[] de tamaño N y una array Q[] que consta de M consultas de tipo {L, R} , la tarea es imprimir el recuento de tripletes cuyo XOR tiene un número par de bits establecidos en el rango [ L, R] , para cada una de las M consultas.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}, N = 5, Q[] = {{1, 4}, {3, 4}}, M = 2
Salida: 3
              0
Explicación:
Ejecutar la consulta de la siguiente manera:

1. Consulta(1, 4): Imprimir 3. Los tripletes cuyo xor tiene un número par de bits establecidos son {1, 2, 3}, {1, 3, 4} y {2, 3, 4}.
2. Consulta(3, 4): Imprime 0. No hay tripletas que cumplan la condición.

Entrada: arr[] = {3, 3, 3}, N = 2, Q[] = {{1, 3}}, M = 1
Salida: 1

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones: 

1. El XOR de dos números X e Y , es decir , X^Y, puede tener un número par de bits establecidos solo si:
   1. Tanto X como Y tienen un número par de bits establecidos .
   2. Tanto X como Y tienen un número impar de bits establecidos .
2. Así, solo existen casos, donde el XOR de tres números tiene un número par de bits establecidos , que son:
   1. Los tres números tienen un número par de bits establecidos .
   2. Exactamente dos de ellos tienen un número impar de bits establecidos y el otro tiene un número par de bits establecidos .
3. Por lo tanto, el problema se puede resolver con el concepto de arrays de prefijos aplicando las observaciones anteriores.

Siga los pasos a continuación para resolver el problema:

• Inicialice una array de prefijos, digamos preo[] de tamaño N+1 , donde preo[i] almacena la cantidad de elementos hasta el índice i , que tienen una cantidad impar de bits establecidos .
• Cree otra array de prefijos, por ejemplo , pree de tamaño N+1 , donde pree[i] almacena la cantidad de elementos hasta el índice i , que tienen una cantidad par de bits establecidos.
• Recorra la array arr[] y haga lo siguiente:
  • Utilice la función __builtin_popcount() para calcular el número de bits establecidos en el elemento actual.
  • Si el número de bits establecidos es impar , incremente preo[i]
  • De lo contrario, incremente pree[i]
• Atraviese la array Q[] y realice los siguientes pasos:
  • Calcule el número de elementos que tienen un número impar de bits establecidos y guárdelo en una variable, digamos impar, usando la array preo[] .
  • Calcule el número de elementos que tienen un número par de bits establecidos y guárdelo en una variable, digamos incluso, utilizando la array pree [] .
  • Inicialice una respuesta variable a 0 para almacenar el recuento de trillizos.
  • Si even no es menor que 3 , agregue ^even C ₃ a ans .
  • Si el par no es menor que 1 y el impar no es menor que 2 , agregue ( ^impar C ₂ )*( ^par C ₁ ) a ans .
  • Finalmente, imprima el conteo de tripletes obtenidos en ans para la consulta actual {L, R}.

A continuación se muestra una implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to calculate NCR
int NCR(int N, int R)
{
    if (R > N - R)
        R = N - R;
    int ans = 1;
    for (int i = 1; i <= R; i++) {
        ans *= N - R + i;
        ans /= i;
    }
    return ans;
}
// Function to answer queries about
// the number of triplets  in range
// whose XOR has an even number of
// set bits
void solveXorTriplets(int arr[], int N,
                      vector<pair<int, int> > Q, int M)
{
    // Prefix arrays to store
    // number that have odd
    // and even setbits
    int preo[N + 1] = { 0 };
    int pree[N + 1] = { 0 };
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
        // Update
        preo[i + 1] += preo[i];
        pree[i + 1] += pree[i];
 
        // Find bits in current
        // element
        int setbits = __builtin_popcount(arr[i]);
 
        // If number of setbits
        // is odd
        if (setbits % 2)
            preo[i + 1]++;
        // Otherwise
        else
            pree[i + 1]++;
    }
    // Traverse the query Q[][]
    for (int i = 0; i < M; i++) {
        // Stores Left boundary
        int L = Q[i].first;
        // Stores Right boundary
        int R = Q[i].second;
 
        // Stores number of elements
        // that have odd set bits in
        // the given range
        int odd = preo[R] - preo[L - 1];
 
        // Store number of elements
        // that have even set bits
        // in given range
        int even = pree[R] - pree[L - 1];
 
        // Store the count
        // of the triplets
        int ans = 0;
 
        // If even is greater
        // than ore equal to 3
        if (even >= 3)
            ans += NCR(even, 3);
 
        // If odd is greater than
        // or equal to and even is
        // greater than or equal to
        // 1
        if (odd >= 2 && even >= 1)
            ans += NCR(odd, 2) * NCR(even, 1);
 
        // Print the answer
        // for current query
        cout << ans << endl;
    }
}
// Driver Code
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    vector<pair<int, int> > Q = { { 1, 4 }, { 3, 4 } };
    int M = Q.size();
 
    solveXorTriplets(arr, N, Q, M);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
static class pair
{
    int first, second;
     
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }  
} 
   
// Utility function to calculate NCR
static int NCR(int N, int R)
{
    if (R > N - R)
        R = N - R;
         
    int ans = 1;
     
    for(int i = 1; i <= R; i++)
    {
        ans *= N - R + i;
        ans /= i;
    }
    return ans;
}
 
// Function to answer queries about
// the number of triplets  in range
// whose XOR has an even number of
// set bits
static void solveXorTriplets(int arr[], int N,
                             Vector<pair> Q, int M)
{
     
    // Prefix arrays to store
    // number that have odd
    // and even setbits
    int preo[] = new int[N + 1];
    int pree[] = new int[N + 1];
 
    // Traverse the array arr[]
    for(int i = 0; i < N; i++)
    {
         
        // Update
        preo[i + 1] += preo[i];
        pree[i + 1] += pree[i];
 
        // Find bits in current
        // element
        int setbits = Integer.bitCount(arr[i]);
 
        // If number of setbits
        // is odd
        if (setbits % 2 != 0)
            preo[i + 1]++;
             
        // Otherwise
        else
            pree[i + 1]++;
    }
     
    // Traverse the query Q[][]
    for(int i = 0; i < M; i++)
    {
         
        // Stores Left boundary
        int L = Q.elementAt(i).first;
         
        // Stores Right boundary
        int R =  Q.elementAt(i).second;
 
        // Stores number of elements
        // that have odd set bits in
        // the given range
        int odd = preo[R] - preo[L - 1];
 
        // Store number of elements
        // that have even set bits
        // in given range
        int even = pree[R] - pree[L - 1];
 
        // Store the count
        // of the triplets
        int ans = 0;
 
        // If even is greater
        // than ore equal to 3
        if (even >= 3)
            ans += NCR(even, 3);
 
        // If odd is greater than
        // or equal to and even is
        // greater than or equal to
        // 1
        if (odd >= 2 && even >= 1)
            ans += NCR(odd, 2) * NCR(even, 1);
 
        // Print the answer
        // for current query
        System.out.println(ans);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = arr.length;
 
    Vector<pair> Q = new Vector<>();
      Q.add(new pair(1, 4));
      Q.add(new pair(3, 4));
   
    int M = Q.size();
 
    solveXorTriplets(arr, N, Q, M);
}
}
 
// This code is contributed by Dharanendra L V.

# Python3 program for the above approach
 
 
# Utility function to calculate NCR
def NCR(N, R):
    if (R > N - R):
        R = N - R
    ans = 1
    for i in range(1,R+1):
        ans *= N - R + i
        ans //= i
    return ans
 
# Function to answer queries about
# the number of triplets  in range
# whose XOR has an even number of
# set bits
def solveXorTriplets(arr, N, Q, M):
    # Prefix arrays to store
    # number that have odd
    # and even setbits
    preo = [0]*(N + 1)
    pree = [0]*(N + 1)
 
    # Traverse the array arr[]
    for i in range(N):
        preo[i + 1] += preo[i]
        pree[i + 1] += pree[i]
 
        # Find bits in current
        # element
        setbits =bin(arr[i]).count('1')
 
        # If number of setbits
        # is odd
        if (setbits % 2):
            preo[i + 1] +=1
        # Otherwise
        else:
            pree[i + 1]+=1
 
    # Traverse the query Q[][]
    for i in range(M):
       
        # Stores Left boundary
        L = Q[i][0]
         
        # Stores Right boundary
        R = Q[i][1]
 
        # Stores number of elements
        # that have odd set bits in
        # the given range
        odd = preo[R] - preo[L - 1]
 
        # Store number of elements
        # that have even set bits
        # in given range
        even = pree[R] - pree[L - 1]
 
        # Store the count
        # of the triplets
        ans = 0
 
        # If even is greater
        # than ore equal to 3
        if (even >= 3):
            ans += NCR(even, 3)
 
        # If odd is greater than
        # or equal to and even is
        # greater than or equal to
        # 1
        if (odd >= 2 and even >= 1):
            ans += NCR(odd, 2) * NCR(even, 1)
 
        # Print answer
        # for current query
        print (ans)
         
# Driver Code
if __name__ == '__main__':
 
    arr = [1, 2, 3, 4, 5]
    N = len(arr)
 
    Q = [ [ 1, 4 ], [ 3, 4 ] ]
    M = len(Q)
 
    solveXorTriplets(arr, N, Q, M)
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class pair{
 
    int first, second;
     
    pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }  
     
    public static int BitCount(int n)
    {
        var count = 0;
        while (n != 0)
        {
            count++;
            n &= (n - 1); //walking through all the bits which are set to one
        }
     
        return count;
    }
       
    // Utility function to calculate NCR
    static int NCR(int N, int R)
    {
        if (R > N - R)
            R = N - R;
             
        int ans = 1;
         
        for(int i = 1; i <= R; i++)
        {
            ans *= N - R + i;
            ans /= i;
        }
        return ans;
    }
     
    // Function to answer queries about
    // the number of triplets  in range
    // whose XOR has an even number of
    // set bits
    static void solveXorTriplets(int[] arr, int N,
                                 List<pair> Q, int M)
    {
         
        // Prefix arrays to store
        // number that have odd
        // and even setbits
        int[] preo = new int[N + 1];
        int[] pree = new int[N + 1];
     
        // Traverse the array arr[]
        for(int i = 0; i < N; i++)
        {
             
            // Update
            preo[i + 1] += preo[i];
            pree[i + 1] += pree[i];
     
            // Find bits in current
            // element
            int setbits = BitCount(arr[i]);
     
            // If number of setbits
            // is odd
            if (setbits % 2 != 0)
                preo[i + 1]++;
                 
            // Otherwise
            else
                pree[i + 1]++;
        }
         
        // Traverse the query Q[][]
        for(int i = 0; i < M; i++)
        {
             
            // Stores Left boundary
            int L = Q[i].first;
             
            // Stores Right boundary
            int R =  Q[i].second;
     
            // Stores number of elements
            // that have odd set bits in
            // the given range
            int odd = preo[R] - preo[L - 1];
     
            // Store number of elements
            // that have even set bits
            // in given range
            int even = pree[R] - pree[L - 1];
     
            // Store the count
            // of the triplets
            int ans = 0;
     
            // If even is greater
            // than ore equal to 3
            if (even >= 3)
                ans += NCR(even, 3);
     
            // If odd is greater than
            // or equal to and even is
            // greater than or equal to
            // 1
            if (odd >= 2 && even >= 1)
                ans += NCR(odd, 2) * NCR(even, 1);
     
            // Print the answer
            // for current query
            Console.WriteLine(ans);
        }
    }
     
    // Driver Code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5 };
        int N = arr.Length;
     
        List<pair> Q = new List<pair>();
          Q.Add(new pair(1, 4));
          Q.Add(new pair(3, 4));
       
        int M = Q.Count;
     
        solveXorTriplets(arr, N, Q, M);
    }
}
 
// This code is contributed by ShubhamSingh10

#include <iostream>
using namespace std;
 
int main() {
 
    cout<<"GFG!";
    return 0;
}

<script>
 
// JavaScript program for the above approach
 
function bitCount1(n) {
  return n.toString(2).match(/1/g).length
}
 
// Utility function to calculate NCR
function NCR(N, R)
{
    if (R > N - R)
        R = N - R;
    var ans = 1;
    for (var i = 1; i <= R; i++) {
        ans *= N - R + i;
        ans /= i;
    }
    return ans;
}
// Function to answer queries about
// the number of triplets  in range
// whose XOR has an even number of
// set bits
function solveXorTriplets(arr, N, Q, M)
{
    // Prefix arrays to store
    // number that have odd
    // and even setbits
    var preo = new Array(N+1).fill(0);
    var pree = new Array(N+1).fill(0);
 
    // Traverse the array arr[]
    for (var i = 0; i < N; i++) {
        // Update
        preo[i + 1] += preo[i];
        pree[i + 1] += pree[i];
 
        // Find bits in current
        // element
        var setbits = bitCount1(arr[i]);
 
        // If number of setbits
        // is odd
        if (setbits % 2)
            preo[i + 1]++;
        // Otherwise
        else
            pree[i + 1]++;
    }
    // Traverse the query Q[][]
    for (var i = 0; i < M; i++) {
        // Stores Left boundary
        var L = Q[i][0];
        // Stores Right boundary
        var R = Q[i][1];
 
        // Stores number of elements
        // that have odd set bits in
        // the given range
        var odd = preo[R] - preo[L - 1];
 
        // Store number of elements
        // that have even set bits
        // in given range
        var even = pree[R] - pree[L - 1];
 
        // Store the count
        // of the triplets
        var ans = 0;
 
        // If even is greater
        // than ore equal to 3
        if (even >= 3)
            ans += NCR(even, 3);
 
        // If odd is greater than
        // or equal to and even is
        // greater than or equal to
        // 1
        if (odd >= 2 && even >= 1)
            ans += NCR(odd, 2) * NCR(even, 1);
 
        // Print the answer
        // for current query
        document.write(ans + "<br>");
    }
}
// Driver Code
var arr = [1, 2, 3, 4, 5 ];
var N = arr.length;
 
var Q = [ [ 1, 4 ], [ 3, 4 ] ];
var M = Q.length;
 
solveXorTriplets(arr, N, Q, M);
 
// This code is contributed by Shubhamsingh10
 
</script>

3
0

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