Блог пользователя ThomazL

Автор ThomazL, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ThomazL (previous revision, new revision, compare).

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?