Hi can I ask about the approach to this problem? Thanks!
# | User | Rating |
---|---|---|
1 | jiangly | 3898 |
2 | tourist | 3840 |
3 | orzdevinwang | 3706 |
4 | ksun48 | 3691 |
5 | jqdai0815 | 3682 |
6 | ecnerwala | 3525 |
7 | gamegame | 3477 |
8 | Benq | 3468 |
9 | Ormlis | 3381 |
10 | maroonrk | 3379 |
# | User | Contrib. |
---|---|---|
1 | cry | 168 |
2 | -is-this-fft- | 165 |
3 | Dominater069 | 161 |
4 | Um_nik | 160 |
5 | atcoder_official | 159 |
6 | djm03178 | 157 |
7 | adamant | 153 |
8 | luogu_official | 151 |
9 | awoo | 149 |
10 | TheScrasse | 146 |
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.