Loserinlife's blog

By Loserinlife, history, 12 months ago, In English

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

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

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

| Write comment?
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bump

»
12 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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]$$$.