I_love_Saundarya's blog

By I_love_Saundarya, history, 5 years ago, In English

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 ?

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like 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?

»
5 years ago, # |
Rev. 9   Vote: I like it +9 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Sounds like it’s solvable with wavelet tree.

»
5 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +16 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 tree
Query code for fenwick tree

Then apply MO's algorithm for querying part