各マスについて最初に黒く塗られる時刻を事前に計算しておくことで、この問題は、次の \(2\) 種類のクエリを処理する問題に置き換えることができます。

1. マス \((i,j)\) を黒く塗る（このクエリは \(H W\) 回以下）
2. マス \((i,j)\) と連結なマスをすべて色 \(c\) で塗る

なおこの事前計算はたとえば C++ の set などを用いて「各行について、まだ黒色に塗られていないマスの集合」と「各列について、まだ黒色に塗られていないマスの集合」を管理することで \(O((HW+Q)\log{(H+W)})\) 時間で達成できます。

さらに、クエリを逆順に見ることで次の問題に置き換えることができます。

1. 各マスが無色か黒色であるグリットが与えられる
2. 以下のクエリが与えられる
   1. 黒色で塗られているマス \((i,j)\) を無色にする
   2. マス \((i,j)\) と連結なマスをすべて色 \(c\) で塗る
3. 各マスについて、最初に塗られた色を答える（なければ初期状態の無色か黒色）

この問題は以下のように Union-Find 等を用いて「連結成分をマージする過程の木」を構築することで解くことができます。

初期状態のグリッドを連結成分に分け、各連結成分に対応する頂点を作ります。ただし、黒色のマスも \(1\) つの連結成分として処理します。さらに、各頂点には色の情報を保持します。

クエリを次のように処理します。

• \(1\) つ目のクエリでは、マス \((i,j)\) を上下左右の黒色でないすべてのマスと連結させます。また、新しい連結成分に対応する頂点を作り、元の連結成分に対応する頂点すべての親とします。
• \(2\) つ目のクエリでは、マス \((i,j)\) を含む連結成分に対応する頂点にまだ色が塗られていない場合、その頂点を色 \(c\) で塗ります。

このとき各マスに対する答えは、初期状態におけるそのマスに対応する頂点の、色の塗られた最も低い祖先の色（存在しなければ初期状態の無色か黒色）です。

以上の方法で、この問題を \(O((HW+Q)\log{(H+W)})\) 時間で解くことができます。

クレジット

原案： US_cube

解法： US_cube

問題準備・解説： mono_1729

レビュー： hirakuuuu

テスター： QCFium

校正： ngtkana