概要
Wavelet Matrix は 2 次元空間の点群に関するクエリを処理するデータ構造と見ることが出来ます。
これを発展させて 3 次元空間の点群に関するクエリを で処理するデータ構造が存在します。
出来ること
を非負整数の
つ組の列として、データ構造を構築する。
- 時間計算量
- 空間計算量
は各成分の最大値
で第
成分が
かつ第
成分が
のものの個数を出力する。
- 時間計算量
で第
成分が
のもののうち、第
成分が
番目に小さいものを出力する。
- 時間計算量
アルゴリズム
通常の Wavelet Matrix における の処理は以下のような具合でした。
int ret = 0; for (int p = matrix.size(); p-- != 0;) { bit_vector &vec = matrix[p]; int zeros = vec.rank0(l, r); // この段の [l, r) における 0 の個数 if (zeros <= k) { // 答えの p bit 目は 1 ret |= 1 << p; k -= zeros; l = vec.rank0(0, n) + vec.rank1(0, l); r = vec.rank0(0, n) + vec.rank1(0, r); } else { l = vec.rank0(0, l); r = vec.rank0(0, r); } } return ret;
第 成分についての Wavelet Matrix を構築して、
のクエリを処理することを考えます。
と異なるのは、
zeros
を計算する部分のみです。
この部分を、第 成分が
の要素に限定して数えることが出来れば、全く同様の処理を行うことが出来ます。
格段について、bitvector が 0 の成分だけ抜き出して第
成分についての Wavelet Matrix を構築すれば、求める値を計算することが可能です。
もほとんど同様です: 第
成分について通常の処理をしながら、答えに加算する時だけ第
成分を考慮した値を足し上げます。
実装例
Submission #23120967 - AtCoder Beginner Contest 203(Sponsored by Panasonic)
ABC203 D - Pond に提出して TLE したものです。