Dada una array ‘a[]’ de tamaño n y número de consultas q. Cada consulta se puede representar mediante dos números enteros l y r. Su tarea es imprimir el número de enteros distintos en el subarreglo l a r. Dado a[i] <= 
Ejemplos:
Input : a[] = {1, 1, 2, 1, 2, 3}
q = 3
0 4
1 3
2 5
Output : 2
2
3
In query 1, number of distinct integers
in a[0...4] is 2 (1, 2)
In query 2, number of distinct integers
in a[1..3] is 2 (1, 2)
In query 3, number of distinct integers
in a[2..5] is 3 (1, 2, 3)
Input : a[] = {7, 3, 5, 9, 7, 6, 4, 3, 2}
q = 4
1 5
0 4
0 7
1 8
output : 5
4
6
7
Sea a[0…n-1] una array de entrada y q[0..m-1] una array de consultas. Acercarse :
- Ordene todas las consultas de manera que
se junten las consultas con valores L de 0 a , luego todas las consultas de 
a 
, y así sucesivamente. Todas las consultas dentro de un bloque se clasifican en orden creciente de valores R. - Inicialice una array freq[] de tamaño con 0 . La array freq[] lleva la cuenta de las frecuencias de todos los elementos que se encuentran en un rango determinado.
- Procese todas las consultas una por una de manera que cada consulta use una cantidad de elementos diferentes y una array de frecuencia calculada en la consulta anterior y almacene el resultado en una estructura.
- Sea ‘curr_Diff_element’ el número de elementos diferentes de la consulta anterior.
- Eliminar elementos adicionales de la consulta anterior. Por ejemplo, si la consulta anterior es [0, 8] y la consulta actual es [3, 9], elimine a [0], a [1] y a [2]
- Agregar nuevos elementos de la consulta actual. En el mismo ejemplo anterior, agregue a[9].
- Ordene las consultas en el mismo orden en que se proporcionaron anteriormente e imprima sus resultados almacenados
Agregando elements()
- Aumente la frecuencia del elemento que se agregará (freq[a[i]]) en 1.
- Si la frecuencia del elemento a[i] es 1, aumente curr_diff_element en 1 ya que se ha agregado 1 nuevo elemento en el rango.
Eliminando elements()
- Disminuya la frecuencia del elemento a eliminar (a[i]) en 1.
- si la frecuencia de un elemento a[i] es 0. Simplemente disminuya curr_diff_element en 1 ya que 1 elemento se ha eliminado por completo del rango.
Nota: En este algoritmo, en el paso 2, la variable de índice para R cambia como máximo O(n * ) veces a lo largo de la ejecución y lo mismo para L cambia su valor como máximo O(m * ) veces. Todos estos límites son posibles solo porque las consultas ordenadas primero en bloques de tamaño. La parte de preprocesamiento toma un tiempo O(m Log m). El procesamiento de todas las consultas requiere O(n * ) + O(m * ) = O((m+n) * ) tiempo. A continuación se muestra la implementación del enfoque anterior:
CPP
// Program to compute no. of different elements
// of ranges for different range queries
#include <bits/stdc++.h>
using namespace std;
// Used in frequency array (maximum value of an
// array element).
const int MAX = 1000000;
// Variable to represent block size. This is made
// global so compare() of sort can use it.
int block;
// Structure to represent a query range and to store
// index and result of a particular query range
struct Query {
int L, R, index, result;
};
// Function used to sort all queries so that all queries
// of 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;
}
// calculate distinct elements of all query ranges.
// m is number of queries n is size of array a[].
void queryResults(int a[], int n, Query q[], int m)
{
// 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
// different elements
int currL = 0, currR = 0;
int curr_Diff_elements = 0;
// Initialize frequency array with 0
int freq[MAX] = { 0 };
// Traverse through all queries
for (int i = 0; i < m; i++) {
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Remove extra elements of previous range.
// For example if previous range is [0, 3]
// and current range is [2, 5], then a[0]
// and a[1] are subtracted
while (currL < L) {
// element a[currL] is removed
freq[a[currL]]--;
if (freq[a[currL]] == 0)
curr_Diff_elements--;
currL++;
}
// Add Elements of current Range
// Note:- during addition of the left
// side elements we have to add currL-1
// because currL is already in range
while (currL > L) {
freq[a[currL - 1]]++;
// include a element if it occurs first time
if (freq[a[currL - 1]] == 1)
curr_Diff_elements++;
currL--;
}
while (currR <= R) {
freq[a[currR]]++;
// include a element if it occurs first time
if (freq[a[currR]] == 1)
curr_Diff_elements++;
currR++;
}
// Remove elements of previous range. For example
// when previous range is [0, 10] and current range
// is [3, 8], then a[9] and a[10] are subtracted
// Note:- Basically for a previous query L to R
// currL is L and currR is R+1. So during removal
// of currR remove currR-1 because currR was
// never included
while (currR > R + 1) {
// element a[currL] is removed
freq[a[currR - 1]]--;
// if occurrence of a number is reduced
// to zero remove it from list of
// different elements
if (freq[a[currR - 1]] == 0)
curr_Diff_elements--;
currR--;
}
q[i].result = curr_Diff_elements;
}
}
// print the result of all range queries in
// initial order of queries
void printResults(Query q[], int m)
{
sort(q, q + m, compare1);
for (int i = 0; i < m; i++) {
cout << "Number of different elements" <<
" in range " << q[i].L << " to "
<< q[i].R << " are " << q[i].result << endl;
}
}
// Driver program
int main()
{
int a[] = { 1, 1, 2, 1, 3, 4, 5, 2, 8 };
int n = sizeof(a) / sizeof(a[0]);
Query q[] = { { 0, 4, 0, 0 }, { 1, 3, 1, 0 },
{ 2, 4, 2, 0 } };
int m = sizeof(q) / sizeof(q[0]);
queryResults(a, n, q, m);
printResults(q, m);
return 0;
}
Java
//Java program to compute no. of different elements
// of ranges for different range queries
import java.io.*;
import java.util.*;
class GFG {
// Class to represent a query range and to store
// index and result of a particular query range
public static class Query{
int L, R, index, result;
Query(int l, int r, int i, int res){
this.L = l;
this.R = r;
this.index = i;
this.result = res;
}
}
// Used in frequency array (maximum value of an
// array element).
public static int MAX = 1000000;
// Variable to represent block size. This is made
// global so compare() of sort can use it.
public static int block;
// calculate distinct elements of all query ranges.
// m is number of queries n is size of array a[].
public static void queryResults(int a[], int n, Query q[], int m)
{
// Find block size
block = (int)Math.sqrt(n);
// Sort all queries so that all queries
// of same block are arranged together and within a block,
// queries are sorted in increasing order of R values.
Arrays.sort(q, new Comparator<Query>() {
public int compare(Query x, Query y) {
// Different blocks, sort by block.
if (x.L / block != y.L / block)
return x.L / block < y.L / block?1:-1;
// Same block, sort by R value
return x.R < y.R?1:-1;
}
});
// Initialize current L, current R and current
// different elements
int currL = 0, currR = 0;
int curr_Diff_elements = 0;
// Initialize frequency array with 0
int freq[] = new int[MAX];
Arrays.fill(freq,0);
// Traverse through all queries
for (int i = 0; i < m; i++) {
// L and R values of current range
int L = q[i].L, R = q[i].R;
// Remove extra elements of previous range.
// For example if previous range is [0, 3]
// and current range is [2, 5], then a[0]
// and a[1] are subtracted
while (currL < L) {
// element a[currL] is removed
freq[a[currL]]--;
if (freq[a[currL]] == 0) {
curr_Diff_elements--;
}
currL++;
}
// Add Elements of current Range
// Note:- during addition of the left
// side elements we have to add currL-1
// because currL is already in range
while (currL > L) {
freq[a[currL - 1]]++;
// include a element if it occurs first time
if (freq[a[currL - 1]] == 1) {
curr_Diff_elements++;
}
currL--;
}
while (currR <= R) {
freq[a[currR]]++;
// include a element if it occurs first time
if (freq[a[currR]] == 1){
curr_Diff_elements++;
}
currR++;
}
// Remove elements of previous range. For example
// when previous range is [0, 10] and current range
// is [3, 8], then a[9] and a[10] are subtracted
// Note:- Basically for a previous query L to R
// currL is L and currR is R+1. So during removal
// of currR remove currR-1 because currR was
// never included
while (currR > R + 1) {
// element a[currL] is removed
freq[a[currR - 1]]--;
// if occurrence of a number is reduced
// to zero remove it from list of
// different elements
if (freq[a[currR - 1]] == 0){
curr_Diff_elements--;
}
currR--;
}
q[i].result = curr_Diff_elements;
}
}
// print the result of all range queries in
// initial order of queries
public static void printResults(Query q[], int m)
{
// FSort all queries in order of their
// index value so that results of queries can be printed
// in same order as of input
Arrays.sort(q, new Comparator<Query>() {
public int compare(Query x, Query y) {
return (x.index < y.index)?-1:1;
}
});
for (int i = 0; i < m; i++) {
System.out.println("Number of different elements in range " + q[i].L + " to " + q[i].R + " are " + q[i].result);
}
}
//Driver Code
public static void main (String[] args) {
int a[] = { 1, 1, 2, 1, 3, 4, 5, 2, 8 };
int n = a.length;
Query q[] = new Query[3];
q[0]=new Query(0,4,0,0);
q[1] = new Query(1, 3, 1, 0);
q[2] = new Query( 2, 4, 2, 0);
int m = q.length;
queryResults(a, n, q, m);
printResults(q, m);
}
}
//This code is contributed by shruti456rawal
Producción:
Number of different elements in range 0 to 4 are 3 Number of different elements in range 1 to 3 are 2 Number of different elements in range 2 to 4 are 3
Publicación traducida automáticamente
Artículo escrito por saurabh faujdar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA