Dada una array ‘a[]’ y un número de consultas q. Cada consulta se puede representar mediante l, r, x. Su tarea es imprimir el número de elementos menores o iguales a x en el subarreglo representado por l a r. Ejemplos:
Input : arr[] = {2, 3, 4, 5}
q = 2
0 3 5
0 2 2
Output : 4
1
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 ingenuo El enfoque ingenuo para cada consulta atraviesa el subarreglo y cuenta el número de elementos que están en el rango dado. Enfoque eficiente La idea es utilizar el árbol de índices binarios . Tenga en cuenta que en los siguientes pasos x es el número según el cual debe encontrar los elementos y el subarreglo está representado por l, r. Paso 1: ordene la array en orden ascendente. Paso 2: ordene las consultas según x en orden ascendente, inicialice la array de bits como 0. Paso 3: comience desde la primera consulta y recorra la array hasta que el valor de la array sea menor que x. Para cada uno de estos elementos, actualice el BIT con un valor igual a 1 Paso 4: consulte la array de BIT en el rango de l a r
CPP
// C++ program to answer queries to count number
// of elements smaller than or equal to x.
#include<bits/stdc++.h>
using namespace std;
// structure to hold queries
struct Query
{
int l, r, x, idx;
};
// structure to hold array
struct ArrayElement
{
int val, idx;
};
// bool function to sort queries according to k
bool cmp1(Query q1, Query q2)
{
return q1.x < q2.x;
}
// bool function to sort array according to its value
bool cmp2(ArrayElement x, ArrayElement y)
{
return x.val < y.val;
}
// updating the bit array
void update(int bit[], int idx, int val, int n)
{
for (; idx<=n; idx +=idx&-idx)
bit[idx] += val;
}
// querying the bit array
int query(int bit[], int idx, int n)
{
int sum = 0;
for (; idx > 0; idx -= idx&-idx)
sum += bit[idx];
return sum;
}
void answerQueries(int n, Query queries[], int q,
ArrayElement arr[])
{
// initialising bit array
int bit[n+1];
memset(bit, 0, sizeof(bit));
// sorting the array
sort(arr, arr+n, cmp2);
// sorting queries
sort(queries, queries+q, cmp1);
// current index of array
int curr = 0;
// array to hold answer of each Query
int ans[q];
// looping through each Query
for (int i=0; i<q; i++)
{
// traversing the array values till it
// is less than equal to Query number
while (arr[curr].val <= queries[i].x && curr<n)
{
// updating the bit array for the array index
update(bit, arr[curr].idx+1, 1, n);
curr++;
}
// Answer for each Query will be number of
// values less than equal to x upto r minus
// number of values less than equal to x
// upto l-1
ans[queries[i].idx] = query(bit, queries[i].r+1, n) -
query(bit, queries[i].l, n);
}
// printing answer for each Query
for (int i=0 ; i<q; i++)
cout << ans[i] << endl;
}
// driver function
int main()
{
// size of array
int n = 4;
// initialising array value and index
ArrayElement arr[n];
arr[0].val = 2;
arr[0].idx = 0;
arr[1].val = 3;
arr[1].idx = 1;
arr[2].val = 4;
arr[2].idx = 2;
arr[3].val = 5;
arr[3].idx = 3;
// number of queries
int q = 2;
Query queries[q];
queries[0].l = 0;
queries[0].r = 2;
queries[0].x = 2;
queries[0].idx = 0;
queries[1].l = 0;
queries[1].r = 3;
queries[1].x = 5;
queries[1].idx = 1;
answerQueries(n, queries, q, arr);
return 0;
}
Producción:
1 4
Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA