F - Rectilinear Polygons Editorial
by 
sugarrr
Hint
\(N=1\) のときについては考えましたか？
一般に解法選択をする上で、弱い制約において解ける解法であることが必要です。
Solution
まず \(N=1\) のときを考えましょう。
\(x\) の昇順に見ていき、各 \(y\) 座標の点が多角形の内部に含まれているか否かを管理することを考えます。
多角形の辺のうち \(y\) 軸に並行な辺のみ考え、\(x\) 座標の昇順に並べ、順番に見ていきます。
今見ている辺の端点を\((X, Y_1),(X, Y_2) (Y_1 \lt Y_2)\) とすると、この辺によって、\([Y_1,Y_2]\) が多角形の内部に含まれているかどうかが切り替わります。
さらに、多角形が単純であることから、\([Y_1,Y_2]\) の一部が多角形の内部に含まれていて一部は含まれていない、ということはあり得ないことが示せます。
すなわち、\([Y_1,Y_2]\) の適当な一点が多角形の内部に含まれていたならば、今見ている辺により \([Y_1,Y_2]\) 全体が多角形の外部となります。
逆に、\([Y_1,Y_2]\) の一点が多角形の内部に含まれていなかったならば、\([Y_1,Y_2]\) 全体が多角形の内部に含まれるようになります。
したがって、「区間全体に \(1\) を加える」「区間全体に \(-1\) を加える」「一点の値を取得する」という操作が高速に行えれば、各 \(y\) 座標の点が多角形の内部に含まれているか否かを管理することができます。
これは、たとえば遅延評価セグメント木(ACLでいう Lazy Segtree )を用いれば良いです。
\(N\) を一般に戻します。
まず、それぞれの多角形ごとに先述の操作をすることで、(\(y\) 軸に並行な)辺を \(2\) 種類に分類します。
クエリに答えるためには各 \(y\) 座標の点がいくつの多角形の内部に含まれているかを管理すれば良いですが、これは先程と同様に「区間全体に \(1\) を加える」「区間全体に \(-1\) を加える」「一点の値を取得する」という操作が高速に行えれば十分です。
以上より、クエリを先読みして、クエリと(\(y\) 軸に並行な)辺を \(x\) の昇順に並べて順番に見ていくことで、この問題を解くことができました。
posted:
last update: