| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Query problems involving calculating GCD or LCM in a range?
How can we solve this kind of problem efficiently? Does any other data structure also helps in solving these kinds of problems? Some hints might be helpful. Even links to blog or papers. Thanks.
Well, I believe segment tree can handle all associative operations (but some only with point update. As GCD and LCM are associative you can write a simple segment tree and replace your query operation (min/max, sum, ...) with GCD or LCM.
Sry, u r not wrong, but still segment tree is stronk.
But make sure that gcd range update query(like +smth) is possible.
Thanks for replying. I will try to implement it if I do face problems then I will ask you in message.
BTW I have just started learning segment tree , BIT, Treap and Splay and so was curious to know how it helps so much. For some people its looks stupid question. No need to downvote, If you want to remove it from recent action, then you can tell me i will remove it depending on the request priority.