Dada una array de N números, la tarea es responder Q consultas del siguiente tipo:
query(start, end) = Number of times a number x occurs exactly x times in a subarray from start to end
Ejemplos:
Entrada: arr = {1, 2, 2, 3, 3, 3}
Consulta 1: inicio = 0, final = 1,
Consulta 2: inicio = 1, final = 1,
Consulta 3: inicio = 0, final = 2,
Consulta 4: inicio = 1, final = 3,
Consulta 5: inicio = 3, final = 5,
Consulta 6: inicio = 0, final = 5
Salida: 1 0 2 1 1 3
Explicación
En Consulta 1, el elemento 1 aparece una vez en subarreglo [1, 2];
En la consulta 2, ningún elemento satisface la condición requerida es subarreglo [2];
En la consulta 3, el elemento 1 aparece una vez y el 2 dos veces en el subarreglo [1, 2, 2];
En la consulta 4, el elemento 2 aparece dos veces en el subarreglo [2, 2, 3];
En la consulta 5, el elemento 3 aparece tres veces en el subarreglo [3, 3, 3];
En la consulta 6, el elemento 1 aparece una vez, el 2 aparece dos veces y el 3 aparece tres veces en el subarreglo [1, 2, 2, 3, 3, 3]
Método 1 (Fuerza bruta)
Calcule la frecuencia de cada elemento en el subarreglo bajo cada consulta. Si cualquier número x tiene una frecuencia x en el subarreglo cubierto por cada consulta, incrementamos el contador.
C++
/* C++ Program to answer Q queries to
find number of times an element x
appears x times in a Query subarray */
#include <bits/stdc++.h>
using namespace std;
/* Returns the count of number x with
frequency x in the subarray from
start to end */
int solveQuery(int start, int end, int arr[])
{
// map for frequency of elements
unordered_map<int, int> frequency;
// store frequency of each element
// in arr[start; end]
for (int i = start; i <= end; i++)
frequency[arr[i]]++;
// Count elements with same frequency
// as value
int count = 0;
for (auto x : frequency)
if (x.first == x.second)
count++;
return count;
}
int main()
{
int A[] = { 1, 2, 2, 3, 3, 3 };
int n = sizeof(A) / sizeof(A[0]);
// 2D array of queries with 2 columns
int queries[][3] = { { 0, 1 },
{ 1, 1 },
{ 0, 2 },
{ 1, 3 },
{ 3, 5 },
{ 0, 5 } };
// calculating number of queries
int q = sizeof(queries) / sizeof(queries[0]);
for (int i = 0; i < q; i++) {
int start = queries[i][0];
int end = queries[i][1];
cout << "Answer for Query " << (i + 1)
<< " = " << solveQuery(start,
end, A) << endl;
}
return 0;
}
Java
/* Java Program to answer Q queries to
find number of times an element x
appears x times in a Query subarray */
import java.util.HashMap;
import java.util.Map;
class GFG
{
/* Returns the count of number x with
frequency x in the subarray from
start to end */
static int solveQuery(int start, int end, int arr[])
{
// map for frequency of elements
Map<Integer,Integer> mp = new HashMap<>();
// store frequency of each element
// in arr[start; end]
for (int i = start; i <= end; i++)
mp.put(arr[i],mp.get(arr[i]) == null?1:mp.get(arr[i])+1);
// Count elements with same frequency
// as value
int count = 0;
for (Map.Entry<Integer,Integer> entry : mp.entrySet())
if (entry.getKey() == entry.getValue())
count++;
return count;
}
// Driver code
public static void main(String[] args)
{
int A[] = { 1, 2, 2, 3, 3, 3 };
int n = A.length;
// 2D array of queries with 2 columns
int [][]queries = { { 0, 1 },
{ 1, 1 },
{ 0, 2 },
{ 1, 3 },
{ 3, 5 },
{ 0, 5 } };
// calculating number of queries
int q = queries.length;
for (int i = 0; i < q; i++)
{
int start = queries[i][0];
int end = queries[i][1];
System.out.println("Answer for Query " + (i + 1)
+ " = " + solveQuery(start,
end, A));
}
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 Program to answer Q queries
# to find number of times an element x
# appears x times in a Query subarray
import math as mt
# Returns the count of number x with
# frequency x in the subarray from
# start to end
def solveQuery(start, end, arr):
# map for frequency of elements
frequency = dict()
# store frequency of each element
# in arr[start end]
for i in range(start, end + 1):
if arr[i] in frequency.keys():
frequency[arr[i]] += 1
else:
frequency[arr[i]] = 1
# Count elements with same
# frequency as value
count = 0
for x in frequency:
if x == frequency[x]:
count += 1
return count
# Driver code
A = [1, 2, 2, 3, 3, 3 ]
n = len(A)
# 2D array of queries with 2 columns
queries = [[ 0, 1 ], [ 1, 1 ],
[ 0, 2 ], [ 1, 3 ],
[ 3, 5 ], [ 0, 5 ]]
# calculating number of queries
q = len(queries)
for i in range(q):
start = queries[i][0]
end = queries[i][1]
print("Answer for Query ", (i + 1),
" = ", solveQuery(start,end, A))
# This code is contributed
# by Mohit kumar 29
C#
// C# Program to answer Q queries to
// find number of times an element x
// appears x times in a Query subarray
using System;
using System.Collections.Generic;
class GFG
{
/* Returns the count of number x with
frequency x in the subarray from
start to end */
public static int solveQuery(int start,
int end,
int[] arr)
{
// map for frequency of elements
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// store frequency of each element
// in arr[start; end]
for (int i = start; i <= end; i++)
{
if (mp.ContainsKey(arr[i]))
mp[arr[i]]++;
else
mp.Add(arr[i], 1);
}
// Count elements with same frequency
// as value
int count = 0;
foreach (KeyValuePair<int,
int> entry in mp)
{
if (entry.Key == entry.Value)
count++;
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int[] A = { 1, 2, 2, 3, 3, 3 };
int n = A.Length;
// 2D array of queries with 2 columns
int[,] queries = {{ 0, 1 }, { 1, 1 },
{ 0, 2 }, { 1, 3 },
{ 3, 5 }, { 0, 5 }};
// calculating number of queries
int q = queries.Length;
for (int i = 0; i < q; i++)
{
int start = queries[i, 0];
int end = queries[i, 1];
Console.WriteLine("Answer for Query " + (i + 1) +
" = " + solveQuery(start, end, A));
}
}
}
// This code is contributed by
// sanjeev2552
Javascript
<script>
/* Javascript Program to answer Q queries to
find number of times an element x
appears x times in a Query subarray */
/* Returns the count of number x with
frequency x in the subarray from
start to end */
function solveQuery(start,end,arr)
{
// map for frequency of elements
let mp = new Map();
// store frequency of each element
// in arr[start; end]
for (let i = start; i <= end; i++)
mp.set(arr[i],mp.get(arr[i]) == null?1:mp.get(arr[i])+1);
// Count elements with same frequency
// as value
let count = 0;
for (let [key, value] of mp.entries())
if (key == value)
count++;
return count;
}
// Driver code
let A=[1, 2, 2, 3, 3, 3];
let n = A.length;
// 2D array of queries with 2 columns
let queries = [[ 0, 1 ], [ 1, 1 ],
[ 0, 2 ], [ 1, 3 ],
[ 3, 5 ], [ 0, 5 ]];
// calculating number of queries
let q = queries.length;
for (let i = 0; i < q; i++)
{
let start = queries[i][0];
let end = queries[i][1];
document.write("Answer for Query " + (i + 1)
+ " = " + solveQuery(start,
end, A)+"<br>");
}
// This code is contributed by unknown2108
</script>
Answer for Query 1 = 1 Answer for Query 2 = 0 Answer for Query 3 = 2 Answer for Query 4 = 1 Answer for Query 5 = 1 Answer for Query 6 = 3
La Complejidad de Tiempo de este método es O(Q * N)
Método 2 (Eficiente)
Podemos resolver este problema usando el Algoritmo de MO .
Asignamos índice inicial, índice final y número de consulta a cada consulta. Cada consulta toma la siguiente forma:
Índice inicial (L) : índice inicial del subarreglo cubierto por la consulta;
Índice final (R) : índice final del subarreglo cubierto por la consulta;
Número de consulta (índice) : dado que las consultas están ordenadas, esto nos indica la posición original de la consulta para que respondamos las consultas en el orden original
En primer lugar, dividimos las consultas en bloques y ordenamos las consultas utilizando un comparador personalizado.
Ahora procesamos las consultas fuera de línea donde mantenemos dos punteros, es decir, MO_RIGHT y MO_LEFT con cada consulta entrante, movemos estos punteros hacia adelante y hacia atrás e insertamos y eliminamos elementos de acuerdo con los índices inicial y final de la consulta actual.
Deje que la respuesta actual sea current_ans .
Siempre que insertamosun elemento incrementamos la frecuencia del elemento incluido, si esta frecuencia es igual al elemento que acabamos de incluir, incrementamos current_ans. Si la frecuencia de este elemento se convierte en (elemento actual + 1), esto significa que antes este elemento se contó en el current_ans cuando era igual a su frecuencia, por lo que necesitamos decrementar current_ans en este caso.
Cada vez que eliminamos/eliminamos un elemento, disminuimos la frecuencia del elemento excluido, si esta frecuencia es igual al elemento que acabamos de excluir, incrementamos current_ans. Si la frecuencia de este elemento se convierte en (elemento actual – 1), esto significa que antes este elemento se contó en current_ans cuando era igual a su frecuencia, por lo que necesitamos disminuir current_ans en este caso.
CPP
/* C++ Program to answer Q queries to
find number of times an element x
appears x times in a Query subarray */
#include <bits/stdc++.h>
using namespace std;
// 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 {
int L, R, index;
};
/* 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;
}
/* Inserts element (x) into current range
and updates current answer */
void add(int x, int& currentAns,
unordered_map<int, int>& freq)
{
// increment frequency of this element
freq[x]++;
// if this element was previously
// contributing to the currentAns,
// decrement currentAns
if (freq[x] == (x + 1))
currentAns--;
// if this element has frequency
// equal to its value, increment
// currentAns
else if (freq[x] == x)
currentAns++;
}
/* Removes element (x) from current
range btw L and R and updates
current Answer */
void remove(int x, int& currentAns,
unordered_map<int, int>& freq)
{
// decrement frequency of this element
freq[x]--;
// if this element has frequency equal
// to its value, increment currentAns
if (freq[x] == x)
currentAns++;
// if this element was previously
// contributing to the currentAns
// decrement currentAns
else if (freq[x] == (x - 1))
currentAns--;
}
/* Utility Function to answer all queries
and build the ans array in the original
order of queries */
void queryResultsUtil(int a[], Query q[],
int ans[], int m)
{
// map to store freq of each element
unordered_map<int, int> freq;
// Initialize current L, current R
// and current sum
int currL = 0, currR = 0;
int currentAns = 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;
int index = q[i].index;
// 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
// removed
while (currL < L) {
remove(a[currL], currentAns, freq);
currL++;
}
// Add Elements of current Range
while (currL > L) {
currL--;
add(a[currL], currentAns, freq);
}
while (currR <= R) {
add(a[currR], currentAns, freq);
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 Removed
while (currR > R + 1) {
currR--;
remove(a[currR], currentAns, freq);
}
// Store current ans as the Query ans for
// Query number index
ans[index] = currentAns;
}
}
/* Wrapper for queryResultsUtil() and outputs the
ans array constructed by answering all queries */
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);
int* ans = new int[m];
queryResultsUtil(a, q, ans, m);
for (int i = 0; i < m; i++) {
cout << "Answer for Query " << (i + 1)
<< " = " << ans[i] << endl;
}
}
// Driver program
int main()
{
int A[] = { 1, 2, 2, 3, 3, 3 };
int n = sizeof(A) / sizeof(A[0]);
// 2D array of queries with 2 columns
Query queries[] = { { 0, 1, 0 },
{ 1, 1, 1 },
{ 0, 2, 2 },
{ 1, 3, 3 },
{ 3, 5, 4 },
{ 0, 5, 5 } };
// calculating number of queries
int q = sizeof(queries) / sizeof(queries[0]);
// Print result for each Query
queryResults(A, n, queries, q);
return 0;
}
Answer for Query 1 = 1 Answer for Query 2 = 0 Answer for Query 3 = 2 Answer for Query 4 = 1 Answer for Query 5 = 1 Answer for Query 6 = 3
La complejidad temporal de este enfoque utilizando el algoritmo de MO es O(Q * sqrt(N) * logA) donde logA es la complejidad para insertar un elemento A en unordered_map para cada consulta.