Hi can I ask about the approach to this problem? Thanks!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
4 | atcoder_official | 161 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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.