Problem Statement:
You are given an array A of N elements and Q queries. Each query consists of 3 integers L R K . For each query, you have to find the number of elements Ax1, Ax2,….,Axj >= K , where L <= x1, x2,…xj <= R .
Input Format
First line contains an integer N , denoting the number of elements in the array A . Next line contains N integers denoting the elements of the array. Next line contains a single integer Q , denoting the number of queries. Next Q lines contains Q queries, consisting of 3 integers each, L R K .
Constraints
1<=N,Q<=10^5 |Ai|, |K|<=10^9 1<=L, R<=N
Output Format
Print Q lines, where ith line contains the answer to the ith query.
Sample Input
5
1 2 3 4 5
5
1 4 1
1 5 2
1 5 3
1 5 4
1 5 5
Sample Output
4
4
3
2
1
Here’s my code :
#include<bits/stdc++.h>
using namespace std;
vector<int> merge(vector<int> a , vector<int> b){
vector<int> c ;
int i = 0 ;
int j = 0 ;
while(i < a.size() && j < b.size()){
if(a[i] < b[j]){
c.push_back(a[i]) ;
i++ ;
}else{
c.push_back(b[j]) ;
j++ ;
}
}
while(i < a.size()){
c.push_back(a[i]) ;
i++ ;
}
while(j < b.size()){
c.push_back(b[j]) ;
j++ ;
}
// for(auto it = c.begin() ; it!=c.end() ; ++it){
// cout<<*it ;
// }
return c ;
}
int buildST(int arr[] , int s , int e , vector< vector<int> > &tree , int index){
if(s==e){
vector<int> temp ;
temp.push_back(arr[s]) ;
tree[index] = temp ;
return 0 ;
}
int mid = (s+e)/2 ;
buildST(arr ,s , mid , tree , 2*index) ;
buildST(arr ,mid+1 , e , tree , 2*index+ 1) ;
tree[index] = merge(tree[2 * index] , tree[2*index + 1] ) ;
return 0 ;
}
int findmin(vector<vector<int>> tree ,int s , int e , int l , int r , int k , int index){
if(r < s || l > e) return 0 ;
if(l<=s && r>=e){
auto it = lower_bound(tree[index].begin() , tree[index].end() , k) ;
return tree[index].end() - it ;
}
int mid = (s+e)/2 ;
int leftans = findmin(tree , s , mid , l , r , k , 2*index) ;
int rightans = findmin(tree , mid+1 ,e , l , r , k , 2*index+1 ) ;
return leftans + rightans ;
}
int main(){
int n ;
cin>>n ;
int arr[n] ;
for(int i = 0 ; i<n ; ++i){
cin >> arr[i] ;
}
int q ;
cin >> q ;
vector<vector<int>> tree (4*n+1) ;
buildST(arr , 0 , n-1 , tree , 1) ;
while(q--){
int l , r , k ;
cin >> l >> r >> k ;
cout<<findmin(tree , 0 , n-1 , l , r , k , 1) <<"\n";
}
}