| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 161 |
| 2 | adamant | 150 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
Now test to see how large the N has to be for it to be faster than segment trees ;p Though I have to admit, I didn't think it could be made so compact.
Well for N=100000 it is definetely faster :D To test it just overload the < operator and there you go. You can use it with everything as long as you overload < operator. The query returns the position of the minimum.
And I didnt try to optimize it. I just stopped coding when it worked
I think it is faster for N>15000 or something like that. I looked at 282-1-D(birthday) problems test cases
That looks really nice :)
I know
You split array into
blocks of size 
, then build sparse table for each block and for all 
blocks. Am I right?
Yes you are right
But I dont actually build a sparse table like in regular rmq for the small blocks
then there are
sparse tables, each of size 
. Therefore total complexity equals to 
.
In order to build O(N) algorithm you have to go further and group blocks by its types, such that blocks with equal types will have equal sparse tables. It is exactly what Farach-Colton and Bender did
İt is not O(N) bits memory. İt is O(N) in a 32bit system.
As you can see I take 4 vectors, one of them holds the data which is O(N) and N/logN integers in another vector, N integers in another one and 2^(logN) integers which is N in another vector so total memory is O(N)
You are wrong with that part. The small blocks arent sparse tables. Please pay more attention to the code
If you are not satisfied please put a variable in every loop and increment it. And test it with different N. You will see a linear increase.
double post
"block" is a sparse table for log(n) blocks of "data". Right? What do "sblock" and "lookup" exactly do?
sblock is small blocks of size logn and it helps us extract the min in constant time from blocks of size logn
Nice One! But not efficient for large value of N.
This is from an ongoing contest.
UPD: Fixed.
actually its efficiency is the same for all N
Read the topic here e-maxx.ru/algo