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が想定の問題、見たことない。
