Considere una array de tamaño n con valores iniciales 0. ¿Cuántos índices contendrán un valor de al menos x después de realizar m actualizaciones de rango? En cada una de sus consultas, se le da un rango de L a R y debe agregar 1 a cada índice que comienza de L a R (ambos inclusive). Ahora, se le dan q consultas y en cada consulta, un número x. Su tarea es averiguar cuántos índices de array son mayores o iguales que x. (el valor de n, m, q puede ser hasta 10^6)
Ejemplos:
Input : n = 4
l[] = {1, 1, 3};
r[] = {3, 2, 4};
x[] = {1, 4, 2};
Output :
Number of indexes with atleast 1 is 4
Number of indexes with atleast 4 is 0
Number of indexes with atleast 2 is 3
Explanation :
Initial array is {0, 0, 0, 0}
After first update : {1, 1, 1, 0}
After second update : {2, 2, 1, 0}
After third update : {2, 2, 2, 1}
Enfoque ingenuo : la solución trivial que viene a la mente es crear una array de tamaño n y para cada actualización [L, R] agregue 1 a cada índice de array dentro de este rango. Luego, para cada x, cuente, recorriendo toda la array, el número de índices con un valor mayor o igual que x. Sin embargo, sabemos que el valor de n y q es muy grande (hasta 10 ^ 6), por lo que para cada consulta, no podemos simplemente recorrer la array y averiguar cuántos índices tienen al menos x como valor. En el peor de los casos, la complejidad es O(nq), que es bastante ineficiente.
Enfoque eficiente : la idea es calcular primero los valores de la array acumulando todos los incrementos (Usamos la misma técnica que en esta publicación). Después de encontrar elementos, encontramos la frecuencia de cada elemento. Luego calculamos las frecuencias de los elementos más grandes atravesando de derecha a izquierda. Finalmente, podemos responder todas las consultas en tiempo O(1).
C++
// C++ code to count element
// with values at least x.
#include<bits/stdc++.h>
using namespace std;
// For every query in x[0..q-1], count of values
// greater than or equal to query value are printed.
void coutIndices(int n, int l[], int r[], int m,
int x[], int q)
{
// Start and end store frequencies of all
// starting and ending points
int start[n+1] = {0};
int End[n+1] = {0};
for (int i = 0; i < m; i++)
{
start[l[i]] += 1;
End[r[i]] += 1;
}
// Find actual array values after m queries
int compute[n+1] = {0};
compute[1] = start[1];
for (int i = 1; i <= n; i++)
compute[i] = compute[i - 1] + start[i] -
End[i - 1];
// Find frequency of every element in compute[]
int max = *max_element(compute, compute+n+1);
int freq[max+1] = {0};
for (int i=1; i<=n; i++)
freq[compute[i]]++;
// reverse cumulative sum of the freq array
// because of atleast value of array
// indices for each possible x
for (int i = max-1; i >= 0; i--)
freq[i] += freq[i + 1];
// Solving queries
for (int i = 0; i < q; i++)
{
cout << "number of indexes with atleast " <<
x[i] << " is ";
if (x[i] > max)
cout << 0 << "\n";
else
cout << freq[x[i]] << endl;
}
}
// Driver code
int main()
{
// Number of elements in an array
// with all initial 0 values
int n = 7;
// Subarrays that need to be incremented
int l[] = {1, 2, 1, 5};
int r[] = {3, 5, 2, 6};
// Query values
int x[] = {1, 7, 4, 2};
int m = sizeof(l)/sizeof(l[0]);
int q = sizeof(x)/sizeof(x[0]);
coutIndices(n, l, r, m, x, q);
return 0;
}
Java
// Java code to count element
// with values at least x.
import java.io.*;
import java.util.*;
class GFG
{
// For every query in x[0..q-1],
// count of values greater than
// or equal to query value are
// printed.
static void coutIndices(int n, int l[],
int r[], int m,
int x[], int q)
{
// Start and end store
// frequencies of all
// starting and ending points
int []start = new int[n + 1];
int End[] = new int[n + 1];
for (int i = 0; i < m; i++)
{
start[l[i]] += 1;
End[r[i]] += 1;
}
// Find actual array
// values after m queries
int compute[] = new int[n + 1];
compute[1] = start[1];
for (int i = 1; i <= n; i++)
compute[i] = compute[i - 1] +
start[i] -
End[i - 1];
// Find frequency of every
// element in compute[]
Arrays.sort(compute);
int max = compute[n];
int freq[] = new int[max + 1];
for (int i = 1; i <= n; i++)
freq[compute[i]]++;
// reverse cumulative sum of
// the freq array because of
// atleast value of array
// indices for each possible x
for (int i = max - 1; i >= 0; i--)
freq[i] += freq[i + 1];
// Solving queries
for (int i = 0; i < q; i++)
{
System.out.print("number of indexes " +
"with atleast " +
x[i] + " is ");
if (x[i] > max)
System.out.println("0");
else
System.out.println(freq[x[i]]);
}
}
// Driver code
public static void main (String[] args)
{
// Number of elements in
// an array with all
// initial 0 values
int n = 7;
// Subarrays that need
// to be incremented
int l[] = {1, 2, 1, 5};
int r[] = {3, 5, 2, 6};
// Query values
int x[] = {1, 7, 4, 2};
int m = l.length;
int q = x.length;
coutIndices(n, l, r, m, x, q);
}
}
// This code has been
// contributed by anuj_67.
Python3
# Python 3 code to count element with
# values at least x.
# For every query in x[0..q-1], count
# of values greater than or equal to
# query value are printed.
def coutIndices(n, l, r, m, x, q):
# Start and end store frequencies
# of all starting and ending points
start = [0 for i in range(n + 1)]
End = [0 for i in range(n + 1)]
for i in range(0, m, 1):
start[l[i]] += 1
End[r[i]] += 1
# Find actual array values
# after m queries
compute = [0 for i in range(n + 1)]
compute[1] = start[1]
for i in range(1, n + 1, 1):
compute[i] = (compute[i - 1] +
start[i] - End[i - 1])
# Find frequency of every
# element in compute[]
max = compute[0]
for i in range(len(compute)):
if(compute[i] > max):
max = compute[i]
freq = [0 for i in range(max + 1)]
for i in range(1, n + 1, 1):
freq[compute[i]] += 1
# reverse cumulative sum of the freq
# array because of atleast value of
# array indices for each possible x
i = max - 1
while(i >= 0):
freq[i] += freq[i + 1]
i -= 1
# Solving queries
for i in range(0, q, 1):
print("number of indexes with atleast",
x[i], "is", end = " ")
if (x[i] > max):
print(0)
else:
print(freq[x[i]])
# Driver code
if __name__ == '__main__':
# Number of elements in an array
# with all initial 0 values
n = 7
# Subarrays that need to be incremented
l = [1, 2, 1, 5]
r = [3, 5, 2, 6]
# Query values
x= [1, 7, 4, 2]
m = len(l)
q = len(x)
coutIndices(n, l, r, m, x, q);
# This code is contributed by
# Sahil_Shelangia
C#
// C# code to count element
// with values at least x.
using System;
class GFG
{
// For every query in x[0..q-1],
// count of values greater than
// or equal to query value are
// printed.
static void coutIndices(int n, int []l,
int []r, int m,
int []x, int q)
{
// Start and end store
// frequencies of all
// starting and ending points
int []start = new int[n + 1];
int []End = new int[n + 1];
for (int i = 0; i < m; i++)
{
start[l[i]] += 1;
End[r[i]] += 1;
}
// Find actual array
// values after m queries
int []compute = new int[n + 1];
compute[1] = start[1];
for (int i = 1; i <= n; i++)
compute[i] = compute[i - 1] +
start[i] -
End[i - 1];
// Find frequency of every
// element in compute[]
Array.Sort(compute);
int max = compute[n];
int []freq = new int[max + 1];
for (int i = 1; i <= n; i++)
freq[compute[i]]++;
// reverse cumulative sum of
// the freq array because of
// atleast value of array
// indices for each possible x
for (int i = max - 1; i >= 0; i--)
freq[i] += freq[i + 1];
// Solving queries
for (int i = 0; i < q; i++)
{
Console.Write("number of indexes " +
"with atleast " +
x[i] + " is ");
if (x[i] > max)
Console.WriteLine("0");
else
Console.WriteLine(freq[x[i]]);
}
}
// Driver code
public static void Main ()
{
// Number of elements in
// an array with all
// initial 0 values
int n = 7;
// Subarrays that need
// to be incremented
int []l = {1, 2, 1, 5};
int []r = {3, 5, 2, 6};
// Query values
int []x = {1, 7, 4, 2};
int m = l.Length;
int q = x.Length;
coutIndices(n, l, r, m, x, q);
}
}
// This code has been
// contributed by anuj_67.
Javascript
<script>
// Javascript code to count element with values at least x.
// For every query in x[0..q-1],
// count of values greater than
// or equal to query value are
// printed.
function coutIndices(n, l, r, m, x, q)
{
// Start and end store
// frequencies of all
// starting and ending points
let start = new Array(n + 1);
start.fill(0);
let End = new Array(n + 1);
End.fill(0);
for (let i = 0; i < m; i++)
{
start[l[i]] += 1;
End[r[i]] += 1;
}
// Find actual array
// values after m queries
let compute = new Array(n + 1);
compute.fill(0);
compute[1] = start[1];
for (let i = 1; i <= n; i++)
compute[i] = compute[i - 1] +
start[i] -
End[i - 1];
// Find frequency of every
// element in compute[]
compute.sort();
let max = compute[n];
let freq = new Array(max + 1);
freq.fill(0);
for (let i = 1; i <= n; i++)
freq[compute[i]]++;
// reverse cumulative sum of
// the freq array because of
// atleast value of array
// indices for each possible x
for (let i = max - 1; i >= 0; i--)
freq[i] += freq[i + 1];
// Solving queries
for (let i = 0; i < q; i++)
{
document.write("number of indexes " +
"with atleast " +
x[i] + " is ");
if (x[i] > max)
document.write("0" + "</br>");
else
document.write(freq[x[i]] + "</br>");
}
}
// Number of elements in
// an array with all
// initial 0 values
let n = 7;
// Subarrays that need
// to be incremented
let l = [1, 2, 1, 5];
let r = [3, 5, 2, 6];
// Query values
let x = [1, 7, 4, 2];
let m = l.length;
let q = x.length;
coutIndices(n, l, r, m, x, q);
</script>
Producción:
number of indexes with atleast 1 is 6 number of indexes with atleast 7 is 0 number of indexes with atleast 4 is 0 number of indexes with atleast 2 is 4
Publicación traducida automáticamente
Artículo escrito por harsh_sengar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA