This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#include "library/algorithm/mo.hpp"
シグネチャ
Mo(const int n, const std::vector<std::pair<int, int>> &queries)
概要
内部でクエリに答える順番を並び替える.並び替え方は Mo’s algorithm の「おまけ その 1: 定数倍改善」の項を参照.
引数
n
queries
std::vector<std::pair<int, int>>
時間計算量
$Q$ をクエリの数として,$O(Q\log Q)$
// (1) template <typename Eval, typename AddL, typename DelL, typename AddR, typename DelR> auto solve(Eval eval, AddL add_l, DelL del_l, AddR add_r, DelR del_r) // (2) template <typename Eval, typename Add, typename Del> auto solve(Eval eval, Add add, Del del)
$i$ 番目のクエリの答えを $i$ 番目の要素として持つ std::vector を返す.クエリの答えを求めるのに必要な状態を外に置いて,引数の add_l や del_l の中で追加処理や削除処理に応じて状態を更新する.(2) は (1) において add_l = add_r かつ del_l = del_r の場合に用いる.
std::vector
add_l
del_l
add_l = add_r
del_l = del_r
具体的な使用法に関してはテストファイルを参照.
eval : () -> T
add_l : int -> any
del_l : int -> any
add_r : int -> any
del_r : int -> any
返り値
$i$ 番目のクエリの答えを $i$ 番目の要素として持つ std::vector<decltype(eval())>.つまり,std::vector の要素の型は eval() が返す型.
std::vector<decltype(eval())>
eval()
ここでいう $i$ 番目は,クエリの並べ替え前の順番を指す.即ち,外部からは内部の並び替えについては一切意識しなくてもよい.
制約
eval
add_r
del_r
int
eval や add_l などの計算量を $O(1)$ として,$O(N\sqrt Q)$
// (1) int get_left() // (2) int get_right() // (3) std::pair<int, int> get_range()
solve に渡す add_l などの関数内で,現時点の区間を取得したい場合に用いる関数.
現時点の区間は半開区間で $[l,r)$ と表されるとする.
l
r
std::pair<int, int> { l, r }
無し
いずれも $O(1)$
#ifndef SUISEN_MO #define SUISEN_MO #include <algorithm> #include <cmath> #include <numeric> #include <vector> namespace suisen { struct Mo { Mo() = default; Mo(const int n, const std::vector<std::pair<int, int>> &queries) : n(n), q(queries.size()), b(bucket_size(n, q)), qs(queries), ord(q) { std::iota(ord.begin(), ord.end(), 0); std::sort( ord.begin(), ord.end(), [&, this](int i, int j) { const auto &[li, ri] = qs[i]; const auto &[lj, rj] = qs[j]; const int bi = li / b, bj = lj / b; if (bi != bj) return bi < bj; if (ri != rj) return bi & 1 ? ri > rj : ri < rj; return li < lj; } ); } // getter methods used in updating functions: AddL, DelL, etc. auto get_left() const { return l; } auto get_right() const { return r; } auto get_range() const { return std::make_pair(l, r); } auto get_query_id() const { return query_id; } /** * [Parameters] * Eval : () -> T : return the current answer * AddL : int -> any (discarded) : add `l` to the current range [l + 1, r) * DelL : int -> any (discarded) : delete `l` from the current range [l, r) * AddR : int -> any (discarded) : add `r` to the current range [l, r) * DelR : int -> any (discarded) : delete `r` from the current range [l, r + 1) * * [Note] * starting from the range [0, 0). */ template <typename Eval, typename AddL, typename DelL, typename AddR, typename DelR> auto solve(Eval eval, AddL add_l, DelL del_l, AddR add_r, DelR del_r) { l = 0, r = 0; std::vector<decltype(eval())> res(q); for (int qi : ord) { const auto &[nl, nr] = qs[query_id = qi]; while (r < nr) add_r(r), ++r; while (l > nl) --l, add_l(l); while (r > nr) --r, del_r(r); while (l < nl) del_l(l), ++l; res[qi] = eval(); } return res; } /** * [Parameters] * Eval : () -> T : return the current answer * Add : int -> any (discarded) : add `i` to the current range [i + 1, r) or [l, i) * Del : int -> any (discarded) : delete `i` from the current range [i, r) or [l, i + 1) * * [Note] * starting from the range [0, 0). */ template <typename Eval, typename Add, typename Del> auto solve(Eval eval, Add add, Del del) { return solve(eval, add, del, add, del); } private: int n, q, b; int query_id = -1; std::vector<std::pair<int, int>> qs; std::vector<int> ord; int l = 0, r = 0; static int bucket_size(int n, int q) { return std::max(1, int(::sqrt(3) * n / ::sqrt(std::max(1, 2 * q)))); } }; } // namespace suisen #endif // SUISEN_MO
#line 1 "library/algorithm/mo.hpp" #include <algorithm> #include <cmath> #include <numeric> #include <vector> namespace suisen { struct Mo { Mo() = default; Mo(const int n, const std::vector<std::pair<int, int>> &queries) : n(n), q(queries.size()), b(bucket_size(n, q)), qs(queries), ord(q) { std::iota(ord.begin(), ord.end(), 0); std::sort( ord.begin(), ord.end(), [&, this](int i, int j) { const auto &[li, ri] = qs[i]; const auto &[lj, rj] = qs[j]; const int bi = li / b, bj = lj / b; if (bi != bj) return bi < bj; if (ri != rj) return bi & 1 ? ri > rj : ri < rj; return li < lj; } ); } // getter methods used in updating functions: AddL, DelL, etc. auto get_left() const { return l; } auto get_right() const { return r; } auto get_range() const { return std::make_pair(l, r); } auto get_query_id() const { return query_id; } /** * [Parameters] * Eval : () -> T : return the current answer * AddL : int -> any (discarded) : add `l` to the current range [l + 1, r) * DelL : int -> any (discarded) : delete `l` from the current range [l, r) * AddR : int -> any (discarded) : add `r` to the current range [l, r) * DelR : int -> any (discarded) : delete `r` from the current range [l, r + 1) * * [Note] * starting from the range [0, 0). */ template <typename Eval, typename AddL, typename DelL, typename AddR, typename DelR> auto solve(Eval eval, AddL add_l, DelL del_l, AddR add_r, DelR del_r) { l = 0, r = 0; std::vector<decltype(eval())> res(q); for (int qi : ord) { const auto &[nl, nr] = qs[query_id = qi]; while (r < nr) add_r(r), ++r; while (l > nl) --l, add_l(l); while (r > nr) --r, del_r(r); while (l < nl) del_l(l), ++l; res[qi] = eval(); } return res; } /** * [Parameters] * Eval : () -> T : return the current answer * Add : int -> any (discarded) : add `i` to the current range [i + 1, r) or [l, i) * Del : int -> any (discarded) : delete `i` from the current range [i, r) or [l, i + 1) * * [Note] * starting from the range [0, 0). */ template <typename Eval, typename Add, typename Del> auto solve(Eval eval, Add add, Del del) { return solve(eval, add, del, add, del); } private: int n, q, b; int query_id = -1; std::vector<std::pair<int, int>> qs; std::vector<int> ord; int l = 0, r = 0; static int bucket_size(int n, int q) { return std::max(1, int(::sqrt(3) * n / ::sqrt(std::max(1, 2 * q)))); } }; } // namespace suisen