Mogu Mogu (hard)

解説

この問題は、おにぎりの状況を工夫して管理することが求められます。まず愚直におにぎりの状況を配列で管理していた場合、操作1回当たり時間計算量は最大で $O(H+W)$ となるため全体の時間計算量は $O(HW + (H+W)N)$ となり実行時間制限に間に合いません。そのため、残っているおにぎりを別のデータ構造で管理することを考えます。

ここでは、順序付き集合(C++ : std::set) を用いて管理することを考えます。ただし、斜め方向の操作を直交座標上で扱うのは難しいので、あらかじめ座標変換をしておきます。具体的には、$(y,x)$ が与えられたときに $(y+x,y-x)$ という風に座標を変換することで操作を直交座標上と同じように扱うことができます。以後、説明においては返還後の座標 $(X,Y)$ を用います。

さて、残っているおにぎりを順序付き集合(C++ : std::set)を用いて管理することを考えます。具体的には、以下のデータ構造を用います。

• $i$ 番目の要素として、 $X$ 座標が $i$ であるおにぎりの位置を、 $Y$ 座標で持った順序付き集合を持った配列
• $j$ 番目の要素として、 $Y$ 座標が $j$ であるおにぎりの位置を、 $X$ 座標で持った順序付き集合を持った配列

このようにデータ構造を構成し、二分探索(C++ : set::lower_bound関数)を利用することで、各操作を操作1回当たり $O(log(HW)) = O(logH+logW)$ で処理することができます。よって、全体を $O((HW+N)(logH+logW))$ とすることができ、これは時間制限に間に合います。

(Pythonには順序付き集合を扱えるデータ構造がデフォルトで存在しないため、別の解法を用いるかそのようなデータ構造を実装する必要があります。Atcoderにおいては次のSortedSetを用いることが推奨されています。(平衡$\sqrt n$分木だがかなり高速))

• https://github.com/tatyam-prime/SortedSet (tatyam氏)

別解

本解においては順序付き集合を用いましたが、UnionFindを用いても解けます。工夫次第で $O(NlogN)$ まで計算量を改善できます。