I_love_Saundarya's blog

By I_love_Saundarya, history, 4 years ago,

Given multiple queries of the form : "L R k" , how to find the count of numbers less than 'k' in the range {L,R} of the array.

There are no update queries.

N=1000000.

I am not interested in the solution with a merge-sort-tree .

• -18

| Write comment?
 » 4 years ago, # |   0 Constraints?
 » 4 years ago, # |   +3 What is the source of this problem? Please provide a link if possible.
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # | ← Rev. 6 →   +11 If you can process the queries offline you should sort all of the values in the array. After that let's iterate over the sorted values, and add 1 to it's original position in the array using a segment tree, when all values < some k have been added, the answer for the query with that k is the sum on the query's range. Each query costs us log(n) to process thus this approach solves the problem in O(nlogn).If you can't sort the queries offline, i sugest building a mergesort tree over the original array. In each node of the tree you will keep the values of that node's subarray sorted. Now for each query you will need to decompose the range into base nodes, and for each node binary search the number of values
•  » » 4 years ago, # ^ |   +3 What is a mergesort tree ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Basically divide the elements in segments like in a segment tree and for every node you keep all the values in that range sorted. When you do a query like :"number of elements between a and b from l to r" you use the same idea of segment tree to choose the segments and after that you can use binary search to count the number of elements in every range that you are interested in.
•  » » » 4 years ago, # ^ |   +13 I just wrote this code for a merge sort tree that support the query that you wanted. #include using namespace std; template class MergeSortTree{ public: int _l, _r, _m; vector v; MergeSortTree *left, *right; MergeSortTree(int l, int r, vector &e){ _l=l, _r=r, _m=(l+r)/2, v[0]=e[l]; v.resize(r-l+1); if(l==r) left=right=nullptr; else{ left=new MergeSortTree(_l,_m, e); right=new MergeSortTree(_m+1,_r, e); merge(left->v.begin(), left->v.end(), right->v.begin(), right->v.end(), v.begin()); } } int count(int l, int r, t a, t b){ //Number of x -> a<=x<=b and x is between l and r if(l>_r || r<_l) return 0; if(_l>=l && _r<=r) return upper_bound(v.begin(), v.end(), b)-lower_bound(v.begin(), v.end(), a); return left->count(l,r,a,b)+right->count(l,r,a,b); } }; int main(){ vector v={1,5,2,7,4,1}; MergeSortTree mt(0,v.size()-1,v); cout<
 » 4 years ago, # | ← Rev. 2 →   0 You can use policy based data structure to solve this question (ordered_set) in O(N*logN).You can refer to this link to look at this data structure. https://codeforces.com/blog/entry/11080You can also solve it using SQRT Decomposition but you need to be careful about the time limit.
 » 4 years ago, # | ← Rev. 2 →   0 If you really wanna get to it... you can turn each element into a point (i, a[i]) and use an implicit 2d segment tree to query for points in the region where x is [l, r] and y is [k, infinity). O(n log^2 n)Merge sort tree has same time complexity and MUCH better constant factor
 » 4 years ago, # |   0 We can solve this problem Offline. First, sort the queries in increasing order and the values of the array as {value,index}. For each query ,using a data structure which can do sums and update operations (eg segment tree or bit), set to one the all the indices which have value < K of the current query and >= K of the previous query .As you have done this for previous queries the sum query will take into account all values < K.the answer of i'th query is sum(l,r) after performing updates. Here's my submission for a similar problem.
 » 4 years ago, # |   +11 Wavelet tree can solve online version of this problem in O(n*log(maxA)) and offline version in O(n*log(n)) (using compression).Useful links:Errichto's wavelet tree tutorial on YouTubeCodeforces blog with implementation