Hello Everyone,
Given an array ‘a[]’ and number of queries q. Each query can be represented by l, r, x. Your task is to print the number of elements less than or equal to x in the subarray represented by l to r.
Examples:
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)
Note in the following steps x is the number according to which you have to find the elements and the subarray is represented by l, r.
Step 1: Sort the array in ascending order.
Step 2: Sort the queries according to x in ascending order, initialize bit array as 0.
Step 3: Start from the first query and traverse the array till the value in the array is less than equal to x. For each such element update the BIT with value equal to 1
Step 4: Query the BIT array in the range l to r
// C++ program to answer queries to count number
// of elements smaller tban 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;
}
Output:
1
4