| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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(int x,int indx){ while(x<MAX_SIZE){ tree[x]=min(tree[x],indx); x+=x&(-x); } }
query(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