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

Автор Loserinlife, история, 13 месяцев назад, По-английски

Hi can I ask about the approach to this problem? Thanks!

Link: https://dmoj.ca/problem/scp4

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

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

bump

»
13 месяцев назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

I believe there are many solutions to this problem. Anyways, here is my approach.

First, construct a "staircase" of size $$$m$$$ (full of 0s) on top of the grid then rotate everything 45 degrees counter-clockwise. Consider the sample :

the link for the picture in case you can't see it : https://ibb.co/pRTYZFF

If you construct another staircase of size $$$m$$$, full of 0s, at the bottom of the rotated grid, you can see that the red paralellogram is actually a rectangular submatrix of a $$$(n + m) * m$$$ matrix.

Any staircase can be represented as the difference of a green rectangle and a red "rectangle" as in the picture.

More specifically, let $$$A$$$ be the original grid and $$$B$$$ be the $$$(n + m) * m$$$ grid, the green rectangle is $$$(1, c) - (r, c + h - 1)$$$ in $$$A$$$, while the red rectangle is $$$(1, c) - (m + r - c - h, c + h - 1)$$$ in $$$B$$$. (here I'm denoting a rectangle by its top-left and bottom-right points)

We can use two 2D BITs to maintain $$$A$$$ and $$$B$$$ for the (sum of staircase) queries. For update queries $$$(r, c, v)$$$, update $$$[r][c] += v - A[r][c]$$$ in BIT $$$A$$$ and $$$[m + r - c][c] += v - B[m + r - c][c]$$$ in BIT $$$B$$$ and update the new values to $$$A[r][c]$$$ and $$$B[m + r - c][c]$$$.