NCR CodeSprint: Points and Fences

https://www.hackerrank.com/contests/ncr-codesprint/challenges/points-and-fences

問題概要

2次元平面の問題。以下の3種類のクエリを処理する。

  • add x1 y1 x2 y2: (x1,y1) (x2,y2) の長方形型のフェンスを設置する
  • delete j: j番目のクエリで設置したフェンスを除去する
  • query a b: 点 a から点 b に到達可能かどうかを調べる

解法1（ハッシュ）

フェンス 1..Q に対して 64bit のランダムな値 hash[i] を割り当てる。フェンス i を設置する操作を、(x1,y1)から(x2,y2)の長方形領域に hash[i] を xor 加算するとみなす。 点 a から点 b に到達可能であることと、点 a を内包するフェンスの集合と点 b を内包するフェンスの集合が一致することは同値であるため、到達可能であるとき xor 値も一致する。

よって、2次元区間に高速に xor 加算する問題に帰着できた。これは 2D segtree で処理できるが、今回は wavelet matrix で実装してみた。

解法2（分割）

詳しいことは以下の記事を参考に。

Decomposable searching problem - オフラインの場合 - yukicoder

静的な問題は以下で出題されている。

I: Shapes - CODE FESTIVAL 2014 決勝（オープン） | AtCoder

点 a を含む最小の長方形を求める問題は分解可能である。したがって、segtree 上に区間加算 segtree の要領でクエリを載せていき、各ノードで静的問題を解くことで O(n log2 n) 時間で解くことができる。

max で 1.93 sec 掛かっている。真面目に実装すれば速くなるだろう。

解法3 （ハッシュ 2D-segment tree）

このハッシュ解、いろいろ応用が効きそうではある。