In Chinese CSP-S1 today morning, there was a question to use "The Method of Four Russians" to solve RMQ problem. Can anyone do me a favor to teach me what it is? Thank you!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 22:16:51 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
You don't need to learn it now.CCF just had water in it's mind.Don't pay too much attention on that F*** problem
Haha. But the contest is good, I think. I've found that even in Codeforces this Russian website there are few explanations about TMoFR.
You can see that here. (Maybe unfriendly to people unfamiliar to Chinese
And CCF says this algorithm is $$$\Theta(N+Q)$$$ , but OI-wiki says that it should be $$$\Theta(N\log\log N+Q)$$$ ! I think CCF is wrong.
UPD:I didn't see clearly. It should be $$$\Theta(N+Q)$$$
That's a $$$+1/-1$$$ RMQ problem because the depths of adjacent nodes in the euler sequence only can be differ by one. So this algorithm is $$$\Theta (N+Q)$$$.
Oh yes I didn't see that clearly.
Sorry!
Great, is this blog from you? That's nice.
Nope,but OI-wiki.
In a word, I think it's quite not proper to put an Russian alorgithm in a Chinese exam :D
Maybe "The Method of some numbers of Chinese" should be put in.
One of the things you DON'T need to know.
Sure. I even don't know what the Cartesian tree is about.
The Method of Four Russians is a very general technnique, and not just limited to the RMQ. It roughly has to do with "precomputing" the answers for small parts of the problems, and use some other more general structure for the larger parts of the problem.
For instance, in RMQ with The Method of Four Russians, you essentially try to make a sparse table on the range-minima of blocks of small size, and precompute the answers for all small blocks. However, just doing a brute force doesn't work for all small blocks, so rather than solving this for the original problem, we try to find the position of the minimum in equivalence classes of small blocks (which are $$$C_s$$$ in number, where $$$s$$$ is the size of blocks, and $$$C_s$$$ is the $$$s$$$-th Catalan number), which are few in number, and recognize which block each small array corresponds to.
For a more detailed explanation, you can consider reading https://web.stanford.edu/class/cs166/lectures/01/Small01.pdf