きままにものづくり

日々の気付いたことなんかを書いてます。

POJ 3109 : Inner Vertices

問題

無限平面上にN( N \leq 10^5)個の黒点が与えられる。それ以外は白点である。上下左右に黒点がある場合は、その点は黒点になる。黒点の総数を求めよ。

解法

座標圧縮と範囲操作可能なBITを使用する。はじめ、yの値でソートする。その後、逐次xでソートしxに囲まれている範囲( x_i < X < x_j (i < j) )に+1をaddする。現在のxの値のところで、範囲指定のsumを取りcoverがtrueならばansに足し合わせる。
注意点

  • BITの範囲操作をしっかり理解していないと境界で間違える。
  • 座標圧縮のところで、findを使うとTLEする。

計算量

 O( N^2 log N )
N : 要素数
ソートとxの繰り返し回数を大雑把に見積もっているので、実際にはこの計算量より小さい。
Yの値にひとつずつxが分布している場合は、
 O(N log N)
となる。

コード