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 ?

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?

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.

Sounds like it’s solvable with wavelet tree.

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)$$$

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 value

if 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

I think Merge Sort Tree with a small modification can do the job. Answer each query in logarithmic time.

CP-Algorithms Saving entire sub array in each vertex You can learn it from here.

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.

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(x<MAX_SIZE){ tree[x]=min(tree[x],indx); x+=x&(-x); } }

Query code for fenwick treequery(int x){ int ans=INT_MAX; while(x>0){ ans=min(ans,tree[x]); x-=x&(-x); } }

Then apply MO's algorithm for querying part