Editorial for New Year's '18 P8 - Snowy Streets
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, each square has two states: either it can be visited from ~(1, 1)~ or it can't. Also, a square will only change states at most once. Then we can DFS to change the states whenever a square becomes blocked.
Time Complexity: ~\mathcal O(Q+RC)~
For the second subtask, we use the same idea as the first subtask. The only difference is that we need to handle the type 1 operations better. To do this, keep an RMQ segment tree on each row of the grid and lazily update it for each type 1 operation. Then, find the maximum to check whether or not any of the squares in a row became blocked. If so, then you update the blocked squares with ~-\infty~ so that they never show up again.
Time Complexity: ~\mathcal O(QR\log C + RC\log C + RC)~
For the final subtask, keep track of when a square becomes blocked and call this the square's value. The type 2 operations will be answered offline. Call the distance between two squares the minimum value on a path from one to the other. For each square on the middle column, determine the maximum distance from it to every other square. Then, split the grid into two halves along that column. For each of these two new grids, repeat the process. This entire process takes ~\mathcal O(R^2C\log C)~. With these computed numbers, the maximum distance (which can be used to easily determine the answer) for any type 2 operation can be found in ~\mathcal O(R)~. This is done by finding a portion of the grid where one of the squares in the query is on one half of the grid and the other square is on the other half. Then, the computed distances to those two squares from each square of the corresponding middle column can be merged.
Time Complexity: ~\mathcal O(QR\log C + RC\log C + R^2C\log C + QR)~