解説
天気を逆順に処理することを考えます。
マス に最後に雨が流れた日を とすると、最終的な積雪量は 日目より後に に降った雪の合計です。雨が一度も流れてこなかったマスについては、すべての日に降った雪の合計が答えになります。
雪の日には、対応する長方形領域に対して積雪量を 増やします。これは 2次元BIT を用いることで、長方形への加算と1点取得をそれぞれ で処理できます。
雨の日には、始点から DFS または BFS を行います。まだ訪問していないマスに到達したら、その時点でのBITの値をそのマスの答えとして確定させます。このとき、一度訪問したマスは再び探索する必要はないです(あるマスに雨が到達したら、そこから流れる先のすべてのマスにも到達できるため)。DFS・BFS 全体の計算量は です。
最後まで訪問されなかったマスについては、すべての雪の日の処理が終わった時点でのBITの値が答えになります。
以上より、2次元BITによる処理に 、DFS・BFSが なので、全体の計算量は です。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。