Recuento de elementos de paridad par e impar en subarreglo utilizando el algoritmo de MO

Dada una array arr que consta de N elementos y Q consultas representadas por L y R que denotan un rango, la tarea es imprimir el recuento de elementos de paridad par e impar en el subarreglo [L, R] .

Ejemplos:

Entrada:
arr[]=[5, 2, 3, 1, 4, 8, 10]
Q=2
1 3
0 4
Salida:
2 1
3 2

Explicación :
en la consulta 1, los elementos de paridad impar en el subarreglo [1:3] son ​​2 y 1 y el elemento de paridad par es 3.
En la consulta 2, los elementos de paridad impar en el subarreglo [0:4] son ​​2, 1 y 4 y paridad par los elementos son 5 y 3

Entrada:
arr[] = { 13, 17, 12, 10, 18, 19, 15, 7, 9, 6 }
Q=3
1 5
0 7
2 9
Salida:
1 4
3 5
2 6
Explicación :
en la consulta 1, el elemento de paridad impar en el subarreglo [1:4] es 19 y los elementos de paridad par son 17,12,10 y 18.
En la consulta 2, los elementos de paridad impar en el subarreglo [0:7] son ​​13, 19 y 7 y los elementos de paridad par son 17,12,10,18 y 15.
En la consulta 3, los elementos de paridad impar en el subarreglo [2:6] son ​​19 y 7 y los elementos de paridad par son 12,10,18, 15, 9 y 6.

Enfoque:
la idea del algoritmo de MO es preprocesar todas las consultas para que el resultado de una consulta se pueda usar en la siguiente consulta.

1. 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.
2. Cuente los elementos de paridad impar y luego calcule los elementos de paridad par como (R-L+1- elementos de paridad impar)
3. Procese todas las consultas una por una y aumente el recuento de elementos de paridad impar y almacene el resultado en la estructura.

• 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].

Agregando elements()

• Si el elemento actual tiene paridad impar, aumente el recuento de count_oddP .

Eliminando elements()

• Si el elemento actual tiene paridad impar, disminuya el recuento de count_oddP .

El siguiente código es la implementación del enfoque anterior:

C++

// C++ program to count odd and // even parity elements in subarray // using MO's algorithm    #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;      // Ending index     int R;     // Index of query     int 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;            // 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++;         }            q[i].odd = count_oddP;         q[i].even = R - L + 1 - 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, 12 };     int n = sizeof(arr) / sizeof(arr[0]);        Query q[] = { { 1, 3, 0, 0, 0 },                    { 0, 4, 1, 0, 0 },                    { 4, 7, 2, 0, 0 } };        int m = sizeof(q) / sizeof(q[0]);        queryResults(arr, n, q, m);        printResults(q, m);            return 0; }

Producción:

2 1
3 2
2 2

Complejidad temporal: O(Q × √n)