Prerrequisitos: Algoritmo de MO , Descomposición SQRT
Dada una array arr[] de N elementos y dos números enteros A a B , la tarea es responder Q consultas, cada una de las cuales tiene dos números enteros L y R. Para cada consulta, encuentre el número de elementos en el subarreglo arr[L, R] que se encuentra dentro del rango A a B (inclusive).
Ejemplos:
Entrada: arr[] = {3, 4, 6, 2, 7, 1}, A = 1, B = 6, query = {0, 4}
Salida: 4
Explicación:
Todo 3, 4, 6, 2 se encuentra dentro 1 a 6 en el subarreglo {3, 4, 6, 2}
Por lo tanto, la cuenta de tales elementos es 4.Entrada: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}, A = 1, B = 5, query = {3, 5}
Salida: 3
Explicación:
Todos los elementos 3, 4 y 5 se encuentra dentro del rango de 1 a 5 en el subarreglo {3, 4, 5}.
Por lo tanto, la cuenta de tales elementos es 3.
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. A continuación se muestra la ilustración de los pasos:
- Agrupe las consultas en varios fragmentos donde cada fragmento contiene los valores del rango inicial en (0 a √N – 1), (√N a 2x√N – 1), y así sucesivamente. Ordene las consultas dentro de un fragmento en orden creciente de R .
- Procese todas las consultas una por una de manera que cada consulta use el resultado calculado en la consulta anterior.
- Mantenga 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 A = 1, B = 6
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 incrementa 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 entre A y B.
Paso 7: La respuesta es igual a
![\sum_{i=A}^B freq[i]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-df8c9edf3179f337163fc5e0a4ed0936_l3.png "Rendered by QuickLaTeX.com")
Para calcular la suma en el Paso 7, no podemos iterar porque eso conduciría a una complejidad de tiempo O(N) por consulta. Así que usaremos la técnica de descomposición de raíces cuadradas para encontrar la suma, cuya complejidad de tiempo es O(√N) por consulta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// values in the range A to B
// in a subarray of L to R
#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;
};
// 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 A, int B)
{
int ans = 0;
int left_blk, right_blk;
left_blk = getblocknumber(A);
right_blk = getblocknumber(B);
// If left block is equal to right block
// then we can traverse that block
if (left_blk == right_blk) {
for (int i = A; i <= B; i++)
ans += frequency[i];
}
else {
// Traversing first block in
// range
for (int i = A;
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 <= B; 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,
int A, int B)
{
// 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;
// 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("%d\n", getans(A, B));
}
}
// Driver code
int main()
{
int arr[] = { 3, 4, 6, 2, 7, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int A = 1, B = 6;
blk_sz = sqrt(N);
Query Q[] = { { 0, 4 } };
int M = sizeof(Q) / sizeof(Q[0]);
// Answer the queries
queryResults(arr, N, Q, M, A, B);
return 0;
}
Java
// Java implementation to find the
// values in the range A to B
// in a subarray of L to R
import java.util.Arrays;
public class GFG {
static final int MAX = 100001;
static final int SQRSIZE = 400;
// Variable to represent block size.
// This is made global so compare()
// of sort can use it.
static int query_blk_sz;
// Structure to represent a query range
static class Query {
int L;
int R;
public Query(int l, int r)
{
L = l;
R = r;
}
}
// Frequency array
// to keep count of elements
static int[] frequency = new int[MAX];
// Array which contains the frequency
// of a particular block
static int[] blocks = new int[SQRSIZE];
// Block size
static 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.
static boolean 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
static int getblocknumber(int ind)
{
return (ind) / blk_sz;
}
// Function to get the answer
// of range [0, k] which uses the
// sqrt decomposition technique
static int getans(int A, int B)
{
int ans = 0;
int left_blk, right_blk;
left_blk = getblocknumber(A);
right_blk = getblocknumber(B);
// If left block is equal to right block
// then we can traverse that block
if (left_blk == right_blk) {
for (int i = A; i <= B; i++)
ans += frequency[i];
}
else {
// Traversing first block in
// range
for (int i = A; 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 <= B; i++)
ans += frequency[i];
}
return ans;
}
static 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]++;
}
static 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]--;
}
static void queryResults(int a[], int n, Query q[],
int m, int A, int B)
{
// Initialize the block size
// for queries
query_blk_sz = (int)Math.sqrt(m);
// Sort all queries so that queries
// of same blocks are arranged
// together.
Arrays.parallelSort(q, (x, 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;
});
// 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;
// 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++;
}
System.out.println(getans(A, B));
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 4, 6, 2, 7, 1 };
int N = arr.length;
int A = 1, B = 6;
blk_sz = (int)Math.sqrt(N);
Query Q[] = { new Query(0, 4) };
int M = Q.length;
// Answer the queries
queryResults(arr, N, Q, M, A, B);
}
}
// This code is contributed by Lovely Jain
4
Complejidad de tiempo: O(Q*√N)
Complejidad de espacio: O(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