Hi can I ask about the approach to this problem? Thanks!
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3657 |
| 3 | jiangly | 3638 |
| 4 | turmax | 3442 |
| 5 | tourist | 3380 |
| 6 | Um_nik | 3353 |
| 7 | strapple | 3350 |
| 8 | squareOf105 | 3346 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3310 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 135 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
Hi can I ask about the approach to this problem? Thanks!
| Name |
|---|



bump
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]$$$.
Thanks you so much! I will look into it.