解説では \(0\) based index を用います．

[1] 区間情報とその結合

連続する行区間 \([L,R]\) に対して，次の情報を管理することにします．

• 一番上の行の文字列 \(A\)．
• 一番下の行の文字列 \(B\)．
• 上下端の合計 \(2W\) 個のマスの連結関係．

連結関係を表現するデータとしては，Union-Find のデータ構造（AtCoder Library 「DSU」）を思い出しましょう．\(2W\) 個のマスを連結成分分解し，各連結成分についてひとつのマスを代表元として選べば，代表元からなる配列によって連結関係を表すことができます．

区間情報を結合するには，\(2\) つの区間の先頭・末尾の行からなる合計 \(4W\) 個のマスについて Union-Find で連結性を管理すればよいです．

[2] 連結判定クエリ

次に，\(2\) マス \((a,b),(c,d)\) が連結であるかを判定する方法を考えます．\(a\leq c\) としてよいです．

この際単に，区間情報 \([a,c]\) から連結判定をするのは誤りです．\(a\) 行目から \(c\) 行目へのパスは，\(a\) 行目より上のマスや \(c\) 行目より下のマスを通る可能性があるからです．

そこで，グリッドを次の \(3\) つの行区間に分けて考えます．

• 上側：\([0,a]\)
• 中央：\([a,c]\)
• 下側：\([c,N-1]\)

各行区間の情報は，セグメント木の区間積によって取得できます．

\(a\) 行目から \(c\) 行目へのパスは，これらのどれかの区間に含まれるようなパスに分割できるため，これら \(3\) つの区間それぞれでの連結性の情報から，全体での連結性の情報を取得できます．

[3] 解答例

• https://atcoder.jp/contests/aalc001/submissions/79895191