POJ 3109 : Inner Vertices
問題
無限平面上にN()個の黒点が与えられる。それ以外は白点である。上下左右に黒点がある場合は、その点は黒点になる。黒点の総数を求めよ。
解法
座標圧縮と範囲操作可能なBITを使用する。はじめ、yの値でソートする。その後、逐次xでソートしxに囲まれている範囲( )に+1をaddする。現在のxの値のところで、範囲指定のsumを取りcoverがtrueならばansに足し合わせる。
注意点
- BITの範囲操作をしっかり理解していないと境界で間違える。
- 座標圧縮のところで、findを使うとTLEする。
計算量
N : 要素数
ソートとxの繰り返し回数を大雑把に見積もっているので、実際にはこの計算量より小さい。
Yの値にひとつずつxが分布している場合は、
となる。