時空間 Mo （3 次元 Mo, Mo with update）

[hitonanode]

座標の max - min が $N$ でクエリ $Q$ 個のとき最悪 $O(N Q^{2/3})$ になる。

証明： 一辺 $N$ の立方体を各方向に $Q^{1/3}$ 等分して $Q$ 個の小立方体に分割する。各小立方体にクエリが 1 個あるケースを考えるとワーストのコストの下界が作れる。逆に任意のケースに対してこの小立方体ごとにクエリをバケット分割する気持ちになるとワーストのコストがこれで上から抑えられる。

実装方針

• Mo's Algorithm (with update and without update, now you can understand both) - Codeforces
• Mo's algorithm - ei1333の日記
  • (l, r, t) の座標をとって各座標毎に平方分割したとき、 (l, r) の組毎に全ての t を貫くように進んでいくのが特に時空間 Mo と呼ばれている？
• 3d のヒルベルト曲線でソートしてもよいはず（実装は......）
  • spectral3d/hilbert_hpp: C++ hilbert curve implementation.
  • PrincetonLIPS/numpy-hilbert-curve: Numpy implementation of Hilbert curves in arbitrary dimensions
  • Voxel Compression
  • 2d も含めて全部これにしてしまえばいいのでは？
  • 時空間 Mo よりは定数倍が良いか？

問題

• Problem - F - Codeforces
• Problem - G - Codeforces
• Primitive Queries Practice Coding Problem / Practice Coding Problem

[hitonanode]

とりあえず [2308.05673] Algorithms for Encoding and Decoding 3D Hilbert Orderings をガン見したら (x, y, z) -> h は実装できたのでこれでベンチマークしたい