I did the problem COT2(http://www.spoj.com/problems/COT2/) using Mo's Algorithm on trees....Wondering if a solution faster than n*sqrt(n) exists?
№ | Пользователь | Рейтинг |
---|---|---|
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 |
I did the problem COT2(http://www.spoj.com/problems/COT2/) using Mo's Algorithm on trees....Wondering if a solution faster than n*sqrt(n) exists?
Название |
---|
Good day to you!
Well I've done that with MO and it passed (AC).
For MO, follow this tutorial.
Then for each "move" (i.e. increase/decrease boundary of array) you shall be constant [O(1)]. The same is possible for answers.
A very good manner might be to "rename" all numbers so they will fit to 0<= Ai <= N (just sort them and rename them to indices), so you can simply operate over array.
Next thing is to choose good SQRT. Even though I guess any "normal" would do so, I've solved it with "(222)"
So the final complexity was O(Nsqrt(N)) [i.e. no maps, and no other logarithmic operations during MO]
Good Luck & Have Nice Day!
Sorry for a bit confusing language, I was asking if a solution faster than n*sqrt(n) exists or not.. Sorry for inconvenience :)
Oh I'm sorry (misunderstood that Nsqrt(N) was not enough)
Well don't know about any :'(
Auto comment: topic has been updated by virus_1010 (previous revision, new revision, compare).
Am I wrong that you are asking a question related to this problem that is one of problems from a running contest (CodeChef February Challenge 2017)?