考察

愚直に連結成分数を数えるのは、 \(O(N^2 Q)\) 時間となり間に合いません。今回は、このグラフがグリッドであることに注目し、良い構造がないかどうかを観察します。

まず、このグリッドは平面グラフです。よって、辺によって囲まれる領域がいくつかあります（一番外にも領域があると考えます）。

領域を囲む辺を \(1\) つ消去すると、連結成分数が変わらない代わりに領域が \(1\) つ減ります。これを繰り返すと、もともとの領域数を \(r\) として、 \(r-1\) 本の辺を減らして領域数を \(1\) にすることができます。

そこから、異なる連結成分同士の辺を \(1\) つ追加すると（これはグラフがグリッド状であるから可能）、領域数が変わらない代わりに連結成分数が \(1\) 個減ります。よって、もともとの連結成分数を \(a\) とすると \(a-1\) 本の辺を増やして連結成分数を \(1\) にすることができます。

そうして出来たグラフは連結で閉路がないグラフ、すなわち木です。よって頂点数を \(v\) とすると辺の本数は \(v-1\) となります。

式に表すと、もともとの辺の本数を \(e\) として \(e-(r-1)+(a-1) = v-1\) すなわち

\[a = v-e+r-1\]

となります。この式はオイラーの多面体定理としても理解することができます。

以上から、「頂点の数」「辺の数」「領域の数」をそれぞれ数えることでクエリに答えることが出来ます。

「頂点の数」については、問題文中にもある通り \(((D_i-U_i+2)/2) \times ((R_i-L_i+2)/2)\) です。「辺の数」については、辺の個数を累積和に持っておくことで、前計算 \(O(N^2)\) 時間、クエリあたり \(O(1)\) 時間で求めることができます。難しいのは「領域の数」です。

領域の数を数える

双対グラフの考え方を借ります。双対グラフでは、もとのグラフの各領域が頂点となります。偶数 \(x, y\) で表される点たちを考えます。それらについて、点同士が隣接しており、間に辺がない場合にその点たちは同じ領域とみなせます。さらに、点が外につながっている場合、その点は外の領域と同じということにします。

クエリで与えられる部分グリッドについて、領域をなす閉路がその部分グリッドに含まれている場合、その部分グリッドでも領域はそのまま閉じられたままになります。

領域の挙動が変わるのは、もとのグリッドにおいて閉路になっている領域において、部分グリッドがその閉路を一部しか含んでおらず、領域が外とつながっている場合です。そのようなものは部分グリッドの外周の外につながっている部分に限っており、高々 \(4N\) 個しかありません。

「部分グリッドが何個の閉路を含んでいるか？」という問題に高速に答えるためには、各領域について代表点を \(1\) つ決めるとうまくいきます。

これは次のように機能します：

• 部分グリッドが閉路を含んでいるならば、その代表点を必ず含みます。
• 部分グリッドが閉路を全く含んでいないならば、その代表点を必ず含みません。
• 部分グリッドが閉路を一部しか含んでいない場合は、その代表点を含むかもしれないし、含まないかもしれません。しかし、外周の外につながっている部分を全探索することで、領域が外につながっているものの代表点をすべて取り除くことができます。前述のように、 \(4N\) 個の点のみを見ればよいです。

このようにして正確に閉路の個数を数え上げることができます。代表点の個数の累積和を \(O(N^2)\) 時間などで前計算することで、クエリあたり \(O(N)\) でこの問題に答えることができます。

以上から、前計算 \(O(N^2)\) 時間+空間、クエリあたり \(O(N)\) 時間でこの問題に答えることができました。