| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
Suppose an array contains n elements. The elements is in the range 109. We want to know, for every element in the array, the position of the leftmost element that is smaller than that one.
An example:
The array: 20 3 10 5 1 9 100
Answer: 0 0 2 2 0 2 1
Can this problem be done in O(n)?
Auto comment: topic has been updated by Tribbiani (previous revision, new revision, compare).
If we can solve this problem in O(n), we can process q offline "upper_bound" queries to the sorted array of size n in O(n + q). Just reverse this array and add queries to the end. Answers for your problem are precisely these upper bounds.
I can't rigorously prove that it's impossible but i have some ideas. Let's assume that it's possible and construct sorting algorithm that looks to be linear in average.
We need to sort an array a1... an. Let's randomly divide it into two subsequences b1... bk and c1... cn - k. Sort the first sequence. Now let's run hypothetical algorithm for upper bounds: bi is an array, ci are queries. How many elements of cj lies between bi and bi + 1? It seems to be small in average, so we can sort them by any usual algorithm. Overall (average) complexity is f(n) = f(n / 2) + O(n), so f(n) = O(n).
Segment Tree + Co-ordinate Compression in O(N*logN)
Or implicit segment tree, also O(n log n)