Codeforces Round #381 (Div. 1): B. Alyona and a Tree

http://codeforces.com/contest/739/problem/B

解法

u は v の部分木に属するという条件があるので、dist(v,u)≦a[u]という条件は、dist(0,u)-dist(0,v)≦a[u]という条件に書き換えられる。

dist(0,u)-a[u]≦dist(0,v)となるような u の個数を求めればよく、これはオイラーツアーと領域木で処理できる。

fractional cascading を用いた領域木を用いると構築O(n log n)、質問O(log n)でできるようになる。のだが、実測してみたところほとんど早くはならなかった。
遅くなるとしたら構築時間なのだが、普通にクエリが遅かった。

実行速度が気になったので、区間[l,r)にあるx以下の要素を答えることのできるデータ構造3つ

  • wavelet matrix
  • range tree (fractional cascading)
  • range tree (naive)

の速度を比較した。

計測は AtCoder のコードテスト (C++14 GCC 5.3.0) を用いた。計測に用いたコードはこれ。64bit符号なし整数をランダムにn個生成して、その後ランダムな区間に対して q 回クエリをする。n=qとしている。

(追記 2016/11/25)ランダムな区間の生成を間違ってたのでクエリ時間を再測定しました。

測定の結果を表にまとめた。まず構築時間(ms)。

n Wavelet matrix Range tree (fractional cascading) Range tree (naive)
100000 41 34 38
200000 86 75 75
500000 240 165 192
1000000 529 342 389

次にクエリ時間(ms)。

n Wavelet matrix Range tree (fractional cascading) Range tree (naive)
100000 67 201 226
200000 153 433 526
500000 442 2624 1723
1000000 1096 6584 4298

次にメモリ使用量(kByte)。

n Wavelet matrix Range tree (fractional cascading) Range tree (naive)
100000 4548 21216 26196
200000 7976 43616 52592
500000 18536 91040 127568
1000000 36224 189064 261680

予想はしていたが wavelet matrix が速い。構築が若干遅かったが、n=500000で240msなら気にしなくてもよさそう。実装次第でもっと速くなるかも。実をいうと、本来のwavelet matrix は完備辞書というものを使うんだけど、自分は微妙に違うものを使ってる。その影響がどの程度なのかは気になるところ。

そして fractional cascading が遅い。fractional cascading の実装に失敗してるとも思えない。ランダムケースだとまずいとかかな。

何はともあれ、wavelet matrix は速いしメモリ消費も少ないので、領域木を使うよりは wavelet matrix を使った方がいいかもね。空間 O(nlogn/64 + n)。

本題に戻って、この問題の解答コード。余計なものが大量にあるが、愚直な領域木が動いてるだけ。

wavelet matrixが想定の問題、見たことない。