Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

ThomazL's blog

Seg 2D problem: Query using manhattan distance[HELP]
By ThomazL, history, 7 years ago, In English

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?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply