Easy Queries を Wavelet Matrix 3D を用いて解く

https://www.codechef.com/problems/DISTNUM2

参考にしました。http://min-25.hatenablog.com/entry/2017/09/13/073449

要点

  • 2 段目の wavelet matrix は、サイズが小さい方を採用するようにしてある。
  • count に 64 より小さいサイズが渡されたときには愚直を回すようにしてある。64 未満は構築もしていない。
  • ランク辞書を Y 方向 Z 方向共にひとつの完備辞書に格納している。こっちの方が好みというだけで効率的とかそういう意味はない。
  • popcnt が使われるように __attribute__ を付加している。辞書引きはボトルネックになる箇所の一つなので重要っぽい。
  • unlocked 系の io を使用している。しかし、あまり時間短縮に繋がっていない?
  • DFS order でランク辞書をメモリに配置した方がキャッシュ効率がいい?

0.36 秒、41.3 MB。
https://gist.github.com/pekempey/44d0638c2a82480b8648494ee824d275

0.40 秒、32.3 MB。heuristic 1 を使わない分、シンプルに書ける。
https://gist.github.com/pekempey/d03f599122ab7f4ddb7e1dfc95854c64

とりあえず目標にしていた速度には到達した。構築よりはクエリが圧倒的に重く、コードを見た感じでもまだ洗練されていない風に見える。まだ改善できるだろうか?