cp-library
競技プログラミング用 C++ ライブラリ
Mo's Algorithm
data_structure/mo_order.hpp · GitHub で見る
共通ページ
クエリを全て先読みし、区間をまとめて渡します。区間の左端をブロックに分け、右端をブロックごとに昇順・降順へ交互に並べます。区間そのものは変更せず、元のクエリ番号を処理したい順で返します。
#include "lib/data_structure/mo_order.hpp"
std::vector<std::pair<int,int>> ranges{ {0,3}, {2,5}, {0,1} };
auto order = mo_order(ranges);
for (int id : order) {
auto [l,r] = ranges[id];
// 現在の区間を [l,r) へ動かし、答えを answer[id] に保存
}
| 操作 | 内容・返り値 | 計算量 |
|---|---|---|
mo_order(ranges,block_size=0) |
vector<pair<int,int>> の区間を処理する順番を、元の添字の vector<int> で返す |
\(O(Q)\) |
各区間は 0 <= l <= r、区間数は INT_MAX 以下、ブロック幅は非負にします。0 の場合は、左端と右端それぞれの値域の幅と区間数から幅を選びます。空の入力は空の結果を返します。
左端が同じブロックに属し、右端が同じクエリは元の添字順に並びます。
区間数を \(Q\) として、処理順の生成は \(O(Q)\) 時間・空間です。クエリの答えを求めるために区間を動かす時間は含みません。
依存ライブラリ
コード
#ifndef MO_ORDER_HPP
#define MO_ORDER_HPP
#include "../components/radix_sort.hpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
inline std::vector<int> mo_order(const std::vector<std::pair<int, int>>& ranges, int block_size = 0) {
assert(ranges.size() <= std::size_t(std::numeric_limits<int>::max()) && block_size >= 0);
if (ranges.empty()) return {};
int min_l = ranges[0].first, max_l = min_l, min_r = ranges[0].second, max_r = min_r;
for (auto [l, r] : ranges) {
assert(0 <= l && l <= r);
min_l = std::min(min_l, l), max_l = std::max(max_l, l);
min_r = std::min(min_r, r), max_r = std::max(max_r, r);
}
if (!block_size) block_size = std::max(1, int(std::sqrt((double(max_l) - min_l + 1) * (double(max_r) - min_r + 1) / ranges.size())));
std::vector<std::pair<std::uint64_t, int>> keys;
keys.reserve(ranges.size());
for (int i = 0; i < int(ranges.size()); ++i) {
auto [l, r] = ranges[i];
std::uint32_t block = (l - min_l) / block_size;
std::uint32_t right = block & 1 ? ~std::uint32_t(r) : std::uint32_t(r);
keys.emplace_back((std::uint64_t(block) << 32) | right, i);
}
if (keys.size() < 2048) std::sort(keys.begin(), keys.end());
else stable_radix_sort(keys, [](const auto &x) { return x.first; });
std::vector<int> order;
order.reserve(keys.size());
for (auto [key, i] : keys) { (void)key; order.push_back(i); }
return order;
}
#endif
#line 1 "data_structure/mo_order.hpp"
#line 1 "components/radix_sort.hpp"
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <utility>
#include <vector>
template <int Bits, class T, class Key>
void stable_radix_sort(std::vector<T> &values, Key &&key) {
static_assert(1 <= Bits && Bits <= 16);
constexpr unsigned buckets = 1U << Bits, mask = buckets - 1;
using K = std::remove_cvref_t<decltype(key(std::declval<const T &>()))>;
static_assert(std::is_integral_v<K> && std::is_unsigned_v<K> && sizeof(K) <= sizeof(std::uint64_t));
if (values.size() < 2) return;
if (values.size() < 256) {
std::stable_sort(values.begin(), values.end(), [&](const T &a, const T &b) { return key(a) < key(b); });
return;
}
std::uint64_t first = key(values.front()), previous = first, varying = 0;
bool sorted = true;
for (std::size_t i = 1; i < values.size(); ++i) {
std::uint64_t current = key(values[i]);
varying |= first ^ current;
sorted &= previous <= current;
previous = current;
}
if (sorted) return;
std::vector<T> scratch(values.size());
using Counts = std::conditional_t<(Bits <= 11), std::array<std::size_t, buckets>, std::vector<std::size_t>>;
Counts count = [] {
if constexpr (Bits <= 11) return Counts{};
else return Counts(buckets);
}();
for (int shift = 0; shift < 64; shift += Bits) {
if (!((varying >> shift) & mask)) continue;
std::fill(count.begin(), count.end(), 0);
for (const auto &value : values) ++count[(static_cast<std::uint64_t>(key(value)) >> shift) & mask];
std::size_t sum = 0;
for (auto &x : count) {
auto n = x;
x = sum, sum += n;
}
for (auto &&value : values) scratch[count[(static_cast<std::uint64_t>(key(value)) >> shift) & mask]++] = std::move(value);
values.swap(scratch);
}
}
template <class T, class Key>
void stable_radix_sort(std::vector<T> &values, Key key) {
stable_radix_sort<8>(values, std::move(key));
}
namespace radix_sort_detail {
template <int Bits = 8, class T, class Key>
void sort_by_key(std::vector<T> &values, Key key) {
using K = std::remove_cvref_t<decltype(key(std::declval<const T &>()))>;
if constexpr (std::is_integral_v<K> && !std::is_same_v<K, bool> && sizeof(K) <= 8 && std::is_default_constructible_v<T>) {
using U = std::make_unsigned_t<K>;
constexpr U sign = std::is_signed_v<K> ? U(1) << (sizeof(K) * 8 - 1) : U(0);
stable_radix_sort<Bits>(values, [&](const T &value) { return U(U(key(value)) ^ sign); });
} else std::sort(values.begin(), values.end(), [&](const T &a, const T &b) { return key(a) < key(b); });
}
}
#line 6 "data_structure/mo_order.hpp"
#include <cassert>
#include <cmath>
#line 9 "data_structure/mo_order.hpp"
#include <limits>
#line 12 "data_structure/mo_order.hpp"
inline std::vector<int> mo_order(const std::vector<std::pair<int, int>>& ranges, int block_size = 0) {
assert(ranges.size() <= std::size_t(std::numeric_limits<int>::max()) && block_size >= 0);
if (ranges.empty()) return {};
int min_l = ranges[0].first, max_l = min_l, min_r = ranges[0].second, max_r = min_r;
for (auto [l, r] : ranges) {
assert(0 <= l && l <= r);
min_l = std::min(min_l, l), max_l = std::max(max_l, l);
min_r = std::min(min_r, r), max_r = std::max(max_r, r);
}
if (!block_size) block_size = std::max(1, int(std::sqrt((double(max_l) - min_l + 1) * (double(max_r) - min_r + 1) / ranges.size())));
std::vector<std::pair<std::uint64_t, int>> keys;
keys.reserve(ranges.size());
for (int i = 0; i < int(ranges.size()); ++i) {
auto [l, r] = ranges[i];
std::uint32_t block = (l - min_l) / block_size;
std::uint32_t right = block & 1 ? ~std::uint32_t(r) : std::uint32_t(r);
keys.emplace_back((std::uint64_t(block) << 32) | right, i);
}
if (keys.size() < 2048) std::sort(keys.begin(), keys.end());
else stable_radix_sort(keys, [](const auto &x) { return x.first; });
std::vector<int> order;
order.reserve(keys.size());
for (auto [key, i] : keys) { (void)key; order.push_back(i); }
return order;
}