Número de elementos menores o iguales a un número en un subarreglo: Algoritmo de MO

Dada una array arr de tamaño N y Q consultas de la forma L, R y X, la tarea es imprimir el número de elementos menores o iguales a X en el subarreglo representado por L a R.

Prerrequisitos: Algoritmo de MO , Descomposición Sqrt

Ejemplos:

Input: 
arr[] = {2, 3, 4, 5}
Q = {{0, 3, 5}, {0, 2, 2}}
Output:
 4
 1
Explanation:
Number of elements less than or equal to 5
in arr[0..3] is 4 (all elements)

Number of elements less than or equal to 2 
in arr[0..2] is 1 (only 2)

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.
Sea arr[0…n-1] una array de entrada y Q[0..m-1] una array de consultas.

Ordene todas las consultas de manera que las consultas con valores L de 0 a √n – 1 se junten, luego todas 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.
Procese todas las consultas una por una de manera que cada consulta use el resultado calculado en la consulta anterior.
Mantendremos la array de frecuencias que contará la frecuencia de arr[i] tal como aparecen en el rango [L, R].
Por ejemplo: arr[]=[3, 4, 6, 2, 7, 1], L=0, R=4 y X=5

Inicialmente, la array de frecuencia se inicializa en 0, es decir, freq[]=[0….0]
Paso 1 : agregue arr[0] e incremente su frecuencia como freq[arr[0]]++, es decir, freq[3]++
y freq[ ]=[0, 0, 0, 1, 0, 0, 0, 0]
Paso 2 : agregue arr[1] e incremente freq[arr[1]]++, es decir, freq[4]++
y freq[]= [0, 0, 0, 1, 1, 0, 0, 0]
Paso 3 : agregue arr[2] e incremente freq[arr[2]]++, es decir, freq[6]++
y freq[]=[0 , 0, 0, 1, 1, 0, 1, 0]
Paso 4 : agregue arr[3] e incremente freq[arr[3]]++, es decir, freq[2]++
y freq[]=[0, 0 , 1, 1, 1, 0, 1, 0]
Paso 5 : agregue arr[4] e incremente freq[arr[4]]++, es decir, freq[7]++
y freq[]=[0, 0, 1 , 1, 1, 0, 1, 1]
Paso 6– Ahora necesitamos encontrar el número de elementos menores o iguales a X (aquí X=5).
Paso 7 : la respuesta es igual a $\sum_{i=0}^{X} freq[i]$
Para calcular la suma en el paso 7 , no podemos hacer la iteración porque eso conduciría a una complejidad de tiempo O (N) por consulta, por lo que usaremos la técnica de descomposición sqrt para encontrar la suma cuya complejidad de tiempo es O ( √n) por consulta .

C++

// C++ program to answer queries to
// count number of elements smaller
// than or equal to x.
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 100001
#define SQRSIZE 400
 
// Variable to represent block size.
// This is made global so compare()
// of sort can use it.
int query_blk_sz;
 
// Structure to represent a
// query range
struct Query {
 
    int L;
    int R;
    int x;
};
 
// Frequency array
// to keep count of elements
int frequency[MAX];
 
// Array which contains the frequency
// of a particular block
int blocks[SQRSIZE];
 
// Block size
int blk_sz;
 
// 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)
{
    if (x.L / query_blk_sz !=
        y.L / query_blk_sz)
        return x.L / query_blk_sz <
               y.L / query_blk_sz;
 
    return x.R < y.R;
}
 
// Function used to get the block
// number of current a[i] i.e ind
int getblocknumber(int ind)
{
    return (ind) / blk_sz;
}
 
// Function to get the answer
// of range [0, k] which uses the
// sqrt decomposition technique
int getans(int k)
{
    int ans = 0;
    int left_blk, right_blk;
    left_blk = 0;
    right_blk = getblocknumber(k);
 
    // If left block is equal to
    // right block then we can traverse
    // that block
    if (left_blk == right_blk) {
        for (int i = 0; i <= k; i++)
            ans += frequency[i];
    }
    else {
        // Traversing first block in
        // range
        for (int i = 0; i <
             (left_blk + 1) * blk_sz; i++)
            ans += frequency[i];
 
        // Traversing completely overlapped
        // blocks in range
        for (int i = left_blk + 1;
             i < right_blk; i++)
            ans += blocks[i];
 
        // Traversing last block in range
        for (int i = right_blk * blk_sz;
             i <= k; i++)
            ans += frequency[i];
    }
    return ans;
}
 
void add(int ind, int a[])
{
    // Increment the frequency of a[ind]
    // in the frequency array
    frequency[a[ind]]++;
 
    // Get the block number of a[ind]
    // to update the result in blocks
    int block_num = getblocknumber(a[ind]);
 
    blocks[block_num]++;
}
void remove(int ind, int a[])
{
    // Decrement the frequency of
    // a[ind] in the frequency array
    frequency[a[ind]]--;
 
    // Get the block number of a[ind]
    // to update the result in blocks
    int block_num = getblocknumber(a[ind]);
 
    blocks[block_num]--;
}
void queryResults(int a[], int n,
                  Query q[], int m)
{
 
    // Initialize the block size
    // for queries
    query_blk_sz = sqrt(m);
 
    // 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 the
        // current range
 
        int L = q[i].L, R = q[i].R,
                x = q[i].x;
 
        // 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++;
        }
        printf("query[%d, %d, %d] : %d\n",
               L, R, x, getans(x));
    }
}
// Driver code
int main()
{
 
    int arr[] = { 2, 0, 3, 1, 4, 2, 5, 11 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    blk_sz = sqrt(N);
    Query Q[] = { { 0, 2, 2 }, { 0, 3, 5 },
                { 5, 7, 10 } };
 
    int M = sizeof(Q) / sizeof(Q[0]);
     
    // Answer the queries
    queryResults(arr, N, Q, M);
    return 0;
}

Producción:

query[0, 2, 2] : 2
query[0, 3, 5] : 4
query[5, 7, 10] : 2

Complejidad temporal: O(Q × √N) .
Se necesita un tiempo O(Q × √N) para el algoritmo de MO y un tiempo O(Q × √N) para la técnica de descomposición sqrt para responder a la suma de freq[0]+….freq[k], por lo tanto, la complejidad del tiempo total es O( Q × √N + Q × √N) que es O(Q × √N).

Publicación traducida automáticamente

Artículo escrito por saurabhshadow y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Deja una respuesta Cancelar la respuesta