KUPC 2012 G - 村

• 問題
• AC

とりあえずrange tree + fractional cascadingを貼ったらMLEした。

2点の表札が同じであるとき、またその時に限り、それぞれの点$(x,y)$から見てもう一つの点は正方形$[x-2R, x+2R] \times [y-2R, y+2R]$に入っていることに注目して平面走査する^[1]。

各点$(x, y)$についてクエリ$(x, y, \text{"add"}), (x + 2R, y, \text{"delete"})$を用意しておいて、$2N$個のクエリを$x$に関してソートする。あとはクエリの先頭から順に平衡二分木に$y$座標を追加/削除していく。$y$を追加する際に$[y-2R, y+2R]$にすでに点がなければ、新しい表札が必要ということになる。

---

座標の重複があるのでmultisetにあたるものが必要だと思うけど、とりあえず普通のtreapを投げたら通ってしまった。（キーが全部衝突すると深さが${O}(N)$になるのでハック可能なはず。）

---

1. 全部$\pm 2R$でやったが、もちろん$\pm R$でもよい。 ↩︎