Mogu Mogu (easy)

解説

まず、おにぎりのあるグリッドを愚直に管理しようとすると空間計算量が $O(HW)$ となりREしますし、また、各操作での空間計算量が$O(H)$ または $O(W)$ となり、操作の部分だけでも最悪時間計算量は$O(N \times max(H,W))$ となるため確実に実行時間制限に間に合いません。

ここで一つグリッドの管理の方法を工夫してみましょう、おにぎりのあるグリッドはそのグリッドが含まれる行と列のどちらでも操作を行っていないということから、操作を行った行と列をそれぞれ配列で管理すれば空間計算量と時間計算量を $O(N)$ 程度に落とせ、おにぎりが残っているグリッドかどうか調べるクエリは事前に行と列の配列をソートしておくことで二分探索を用いて1クエリ当たり $O(log(N))$ で求めることができます。全体の時間計算量はソート込みで $O((N+Q)log(N))$ となり、今回の制約においては高速です。

別解

操作を行った行と列をそれぞれ配列ではなく集合で管理しても構いません。この場合も全体の時間計算量は $O((N+Q)log(N))$ となり計算量オーダーの面では変わりませんが、行と列を管理する配列への要素の追加とソートを行う部分の時間計算量を $N+NlogN$ から $NlogN$ に落とせるので計算量の定数倍削減ができます。