| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Hi guys,
Today i viewed a, aparently, simple seg2D problem:
SET x y d: Set position (x,y) of the grid to integer d.
QUERY x y d: Return the gcd (Greatest Common Divisor) of all positions of the grid that are at most 'd' positions away (Manhattan Distance) from position (x,y).
But i have no ideia to solve this query type '-'
Can someone help me?
Auto comment: topic has been updated by ThomazL (previous revision, new revision, compare).
How about this? Problem is that we have queries on a rhombus structure. If it were a rectangle or square, 2D segment trees would have worked. But if we modify our matrix and create a rhombus, then rename the indices (i, j), then our queries will be on a square. We can change the shape of matrix to rhombus by adding a special element, say -1 wherever needed. In the gcd function, we can check that if one of the element is -1,return the other element as gcd. Note that we also need to add -1 in between the matrix too, so that the queries on rotated matrix will form a perfect square. Also it would be better then to use 2D sparse table instead of 2D segTree.
Hi.
Just rotate the grid by 45 degrees and use normal 2D segment tree.
To rotate, convert every point (x, y) to (x + y, x - y).
After this rotation, the query will be on the rectangle ((x+d, y+d), (x-d, y-d)). Why it's correct to use a rectangle that gets all positions of the grid that are at most 2 * d after the rotation?