概要
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 したものです。