Dada una array arr[] que consta de N elementos y Q consultas representadas por L , R y K . La tarea es imprimir el recuento de elementos de paridad par e impar en el subarreglo [L, R] después de Bitwise-XOR con K.
Ejemplos:
Entrada: arr[] = {5, 2, 3, 1, 4, 8, 10}
consulta[] = {{0, 5, 3}, {1, 4, 8}, {4, 6, 10}}
Salida:
4 2
1 3
2 1
Explicación:
En la consulta 1, los elementos de paridad par e impar en el subarreglo [0:5] son [2, 1, 4, 8] y [5, 3]. Ahora, después de XOR con K = 3, el número de elementos de paridad par e impar es 4 y 2 respectivamente.
En la consulta 2, los elementos de paridad par e impar en el subarreglo [1:4] son [2, 1, 4] y [3]. Ahora, después de XOR con K = 8, el número de elementos de paridad par e impar es 1 y 3 respectivamente.
En la consulta 3, los elementos de paridad par e impar en el subarreglo [4:6] son [4, 8] y [10]. Ahora, después de XOR con K = 10, el número de elementos de paridad par e impar es 2 y 1 respectivamente.
Enfoque: la idea es usar el algoritmo de MO para preprocesar todas las consultas de modo que el resultado de una consulta se pueda usar en la siguiente consulta.
- Ordene todas las consultas de manera que las consultas con valores L de 0 a √n – 1 se junten, seguidas de las consultas de √n a 2 ×√n – 1 , y así sucesivamente. Todas las consultas dentro de un bloque se clasifican en orden creciente de valores R.
- Cuente los elementos de paridad impar y luego calcule los elementos de paridad par como
- Observación después de XOR con elementos de paridad par e impar:
- XOR de dos elementos de paridad impar es un elemento de paridad par .
- XOR de dos elementos de paridad par es un elemento de paridad par .
- XOR de un elemento de paridad par y otro elemento de paridad impar es un elemento de paridad impar y viceversa.
- Procese todas las consultas una por una y aumente el recuento de elementos de paridad impar y ahora comprobaremos la paridad de K . Si K tiene una paridad par, entonces el recuento de paridad par e impar sigue siendo el mismo , de lo contrario, los intercambiamos .
- Deje que count_oddP almacene el recuento de elementos de paridad impar en la consulta anterior.
- Elimine elementos adicionales de la consulta anterior y agregue nuevos elementos para la consulta actual. Por ejemplo, si la consulta anterior fue [0, 8] y la consulta actual es [3, 9], elimine los elementos arr[0], arr[1] y arr[2] y agregue arr[9].
- Para mostrar los resultados, ordene las consultas en el orden en que se proporcionaron.
Agregar elementos
- Si el elemento actual tiene paridad impar, aumente el recuento de paridad impar.
Quitar elementos
- Si el elemento actual tiene paridad impar, disminuya el recuento de paridad impar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count odd and
// even parity elements in subarray
// after XOR with K
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
// Variable to represent block size.
// This is made global so compare()
// of sort can use it
int block;
// Structure to represent
// a query range
struct Query {
// Starting index
int L, R, K, index;
// Count of odd
// parity elements
int odd;
// Count of even
// parity elements
int even;
};
// To store the count of
// odd parity elements
int count_oddP;
// Function used to sort all queries so that
// all queries of the same block are arranged
// together and within a block, queries are
// sorted in increasing order of R values.
bool compare(Query x, Query y)
{
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block < y.L / block;
// Same block, sort by R value
return x.R < y.R;
}
// Function used to sort all queries
// in order of their index value so
// that results of queries can be
// printed in same order as of input
bool compare1(Query x, Query y)
{
return x.index < y.index;
}
// Function to Add elements
// of current range
void add(int currL, int a[])
{
// _builtin_parity(x)returns true(1)
// if the number has odd parity else
// it returns false(0) for even parity.
if (__builtin_parity(a[currL]))
count_oddP++;
}
// Function to remove elements
// of previous range
void remove(int currR, int a[])
{
// _builtin_parity(x)returns true(1)
// if the number has odd parity else
// it returns false(0) for even parity.
if (__builtin_parity(a[currR]))
count_oddP--;
}
// Function to generate the result of queries
void queryResults(int a[], int n, Query q[],
int m)
{
// Initialize number of odd parity
// elements to 0
count_oddP = 0;
// Find block size
block = (int)sqrt(n);
// Sort all queries so that queries of
// same blocks are arranged together.
sort(q, q + m, compare);
// Initialize current L, current R and
// current result
int currL = 0, currR = 0;
for (int i = 0; i < m; i++) {
// L and R values of current range
int L = q[i].L,
R = q[i].R,
k = q[i].K;
// Add Elements of current range
while (currR <= R) {
add(currR, a);
currR++;
}
while (currL > L) {
add(currL - 1, a);
currL--;
}
// Remove element of previous range
while (currR > R + 1)
{
remove(currR - 1, a);
currR--;
}
while (currL < L) {
remove(currL, a);
currL++;
}
// If parity of K is even
// then the count of odd
// and even parity remains
// the same
if (!__builtin_parity(k)) {
q[i].odd = count_oddP;
q[i].even
= R - L + 1 - count_oddP;
}
// If parity of K is odd
// we swap the count of
// odd and even parity
// elements
else {
q[i].odd
= R - L + 1 - count_oddP;
q[i].even = count_oddP;
}
}
}
// Function to display the results of
// queries in their initial order
void printResults(Query q[], int m)
{
sort(q, q + m, compare1);
for (int i = 0; i < m; i++) {
cout << q[i].odd << " "
<< q[i].even << endl;
}
}
// Driver Code
int main()
{
int arr[] = { 5, 2, 3, 1, 4, 8, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
Query q[] = { { 0, 5, 3, 0, 0, 0 },
{ 1, 4, 8, 1, 0, 0 },
{ 4, 6, 10, 2, 0, 0 } };
int m = sizeof(q) / sizeof(q[0]);
queryResults(arr, n, q, m);
printResults(q, m);
return 0;
}
Java
// Java program to count odd and
// even parity elements in subarray
// after XOR with K
import java.io.*;
import java.util.*;
// Class to represent
// a query range
class Query
{
int L, R, K, index;
// Count of odd
// parity elements
int odd;
// Count of even
// parity elements
int even;
Query(int L, int R, int K,
int index, int odd, int even)
{
this.L = L;
this.R = R;
this.K = K;
this.index = index;
this.odd = odd;
this.even = even;
}
}
class GFG{
// Variable to represent block size.
static int block;
// To store the count of
// odd parity elements
static int count_oddP;
// Function to Add elements
// of current range
static void add(int currL, int a[])
{
// _builtin_parity(x)returns true
// if the number has odd parity else
// it returns false for even parity.
if (__builtin_parity(a[currL]))
count_oddP++;
}
// Function to remove elements
// of previous range
static void remove(int currR, int a[])
{
// _builtin_parity(x)returns true
// if the number has odd parity else
// it returns false for even parity.
if (__builtin_parity(a[currR]))
count_oddP--;
}
// Function to generate the result of queries
static void queryResults(int a[], int n, Query q[],
int m)
{
// Initialize number of odd parity
// elements to 0
count_oddP = 0;
// Find block size
block = (int)(Math.sqrt(n));
// sort all queries so that all queries
// of the same block are arranged together
// and within a block, queries are sorted
// in increasing order of R values.
Arrays.sort(q, (Query x, Query y) ->
{
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block - y.L / block;
// Same block, sort by R value
return x.R - y.R;
});
// Initialize current L, current R and
// current result
int currL = 0, currR = 0;
for(int i = 0; i < m; i++)
{
// L and R values of current range
int L = q[i].L, R = q[i].R, k = q[i].K;
// Add Elements of current range
while (currR <= R)
{
add(currR, a);
currR++;
}
while (currL > L)
{
add(currL - 1, a);
currL--;
}
// Remove element of previous range
while (currR > R + 1)
{
remove(currR - 1, a);
currR--;
}
while (currL < L)
{
remove(currL, a);
currL++;
}
// If parity of K is even
// then the count of odd
// and even parity remains
// the same
if (!__builtin_parity(k))
{
q[i].odd = count_oddP;
q[i].even = R - L + 1 - count_oddP;
}
// If parity of K is odd
// we swap the count of
// odd and even parity
// elements
else
{
q[i].odd = R - L + 1 - count_oddP;
q[i].even = count_oddP;
}
}
}
static boolean __builtin_parity(int K)
{
return (Integer.bitCount(K) % 2) == 1;
}
// Function to display the results of
// queries in their initial order
static void printResults(Query q[], int m)
{
Arrays.sort(q, (Query x, Query y) ->
// sort all queries
// in order of their
// index value so that results
// of queries can be printed
// in same order as of input);
x.index - y.index);
for(int i = 0; i < m; i++)
{
System.out.println(q[i].odd + " " +
q[i].even);
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 5, 2, 3, 1, 4, 8, 10 };
int n = arr.length;
Query q[] = new Query[3];
q[0] = new Query(0, 5, 3, 0, 0, 0);
q[1] = new Query(1, 4, 8, 1, 0, 0);
q[2] = new Query(4, 6, 10, 2, 0, 0);
int m = q.length;
queryResults(arr, n, q, m);
printResults(q, m);
}
}
// This code is contributed by jithin
Producción:
4 2 1 3 2 1
Publicación traducida automáticamente
Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA