| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
I was trying out segment tree problems and had some confusions in understanding the solutions for problems involving segment tree with offline queries.
Here are two problems GQR and 301D - Yaroslav and Divisors, for which I was referring to solutions GQR_AC and 36281412 respectively.
If anyone could help me understand these solutions in detail, it would be a great help.
Thanks!
Can someone please help me?
From what I understand on the question from codeforces, the solution goes something like this: Considering the numbers are different and they are <=2*10^5, he keeps an array in which he keeps the pos[i]= the position of number i in the array. Then, he takes an X from 1 to N and updates positions pos[X], pos[2*X], pos[3*X]... After these updates he then finds the answers for his queries.
"After these updates he then finds the answers for his queries." Can you please elaborate how he found the answer to the queries? This is the part I specifically didn't understand.
Using an Erathosthene's sieve-like technique, he will find all pairs (x,y) so that a[x]%a[y]=0 or a[y]%a[x]=0. Now for each query he has to find the number of pairs fully contained within the interval. This is done with a segment tree as such: go from i=1->n. If a pair is of the form (x,i) with x<=i, then update on position x in the segment tree. If there is a query of the form (x,i) then solve the query. If you need proof that this works, send a message.