### I_love_Saundarya's blog

By I_love_Saundarya, history, 4 years ago,

The problem is as follows(created by me) : -

Given an array of 'n' integers , where n=10^6 , all integers are non-negative.

There are 10^5 queries of the the type :- Q(L,R,X) , which means the first index of a number whose value is less than or equal to x .

Example :- {2,3,4,5,2,1} and Q(2,6,2) = 5 , as a[5]=2 which is <=2 .

Is there any way to solve it ?

• +2

| Write comment?
 » 4 years ago, # | ← Rev. 2 →   0 You want to know index of a number whose value is less than or equal to x in range from L to R? Am i rigth?
 » 4 years ago, # | ← Rev. 9 →   +9 Perhaps you can use Merging tree. First build a Segment tree, each node represents all the elements in the interval (ordered). Let a[i] represent the subscript of elementsi in the interval. There is also an array b in this node which means the Prefix maximum of array a. Then we should traverse the left son first, and lower_bound to find the last place i, whose value <= X. Check, if the b[i] >= L, recursive to the left son, else to the right son. So we can solve every query in O(log^2 n). Sorry for my poor English.
 » 4 years ago, # |   +8 Sounds like it’s solvable with wavelet tree.
 » 4 years ago, # | ← Rev. 3 →   +8 If I have not misunderstood the question, we can use Range Minimum Query with Binary Search to answer the query. Binary search the first index $i$ such that $min(L...i) \leq x$. Assuming no updates, a query can be answered in $O(\log n)$ using a sparse table, with $O(n \log n)$ preprocessing, giving a total of $O((n+q) \log n)$
•  » » 4 years ago, # ^ | ← Rev. 4 →   +16 Btw, one can achieve Q log N, with a segment tree trick as well. So instead of binary searching then querying ur segtree, one should "binary search" inside ur segtree.Brief description:for each range store ur min valueif the min value of our whole range is > x (we will just return R+1 signifying that no such index exists.)then when ur at a range, u can decide to either go left or right.So if the min val in left is <= x, then we can safely go to left. Else we go to the right.(C++ code will look something like): http://ideone.com/2onLzj
 » 4 years ago, # |   +7 I think Merge Sort Tree with a small modification can do the job. Answer each query in logarithmic time.
 » 4 years ago, # |   0 CP-Algorithms Saving entire sub array in each vertex You can learn it from here.
 » 4 years ago, # |   +5 I think it can be solved in a simple way using binary lifting, correct me if I'm wrong.Firstly, consider the following algorithm: start with element a[L], if it is <= X, then we have found the answer, else lets find the first index of an element to the right of a[L], which is < a[L], call it L'. We can solve the same problem for the interval [L', R] (if L' <= R). To speed this algorithm up we first for each element find the next smaller element to the right (for example by using stack in O(n)) and build a binary lifting array with this information. Then we can solve the problem in O(logN) per query in a similar way to the one described above.
 » 4 years ago, # |   0 Break the entire array into $\sqrt{n}$ size blocks. Then build a fenwick tree over each block. tree[x] gives what is the least occurence of values<=x in that block. Update code for fenwick treeupdate(int x,int indx){ while(x0){ ans=min(ans,tree[x]); x-=x&(-x); } }Then apply MO's algorithm for querying part