NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）

　Fを飛ばしてGまでの六完。

コンテストへのリンク

コンテスト後のツイート

NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253） F飛ばしてGまで。
B マンハッタン距離。BFSしようかと思ったが思いとどまった。
C sortedmultiset案件。座標圧縮+BITで解いたが20分+1ペナ
D 包除
E DP。累積和を使う
G 数行まとめてやる場合はまとめて処理できる。

— titia (@titia_til) May 28, 2022

F - Operations on a Matrix

　イベントソートなどと言ったキーワードを見てAC。

　この問題は、

・query 3 i j の直前に現れる query 2 i xがあれば、それを覚える

・上で求めた二つのクエリの間で、query 1 l r x (l<=j<=r) というものの総和を求める

　ということができれば解ける。

　で、二つ目がクエリを後ろから見ることで求められることは分かっていた。

（けれど、ちゃんと、後ろから見て、query 3 i jが出たときに、列jに加わった和をマイナスしなくてはいけないことに気付いていたか？　というと気付いていなかったかもしれない）

　そして、一つ目は、予め求めておけば良いですね。

　こうして整理して書いてみれば気付くのは難しくなく見えるので、ちゃんと整理するのが大事ですね。