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)
このハッシュ解、いろいろ応用が効きそうではある。