static_range_mode.hpp¶
静态半开区间众数：O(N√N) 构建、O(√N) 查询、O(N) 空间，返回众数及频次，并列取最小值，空区间返回空。
Complexity: Time: \(O(n \sqrt{n})\) build and \(O(\sqrt{n})\) query. Space: \(O(1 + n)\), with \(O(1)\) value comparisons and copies.
AC 记录：static_range_mode_query。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n)) query.
/// Space: O(1+n), with O(1) value comparisons and copies.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static half-open range mode queries; ties return the smallest value.
/// Values use strict-weak-order equivalence. The array size fits int.
/// Construction owns its values; queries do not mutate shared scratch state.
template <class T> struct static_range_mode {
int n = 0;
int bs = 1;
int nb = 0;
std::vector<T> xs;
std::vector<int> rk;
std::vector<std::vector<int>> pos;
std::vector<std::vector<int>> md;
std::vector<int> occ;
std::vector<std::vector<int>> mc;
static_range_mode() = default;
explicit static_range_mode(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n = int(a.size());
bs = std::max(1, int(std::sqrt(std::max(1, n))));
nb = n / bs + (n % bs != 0);
std::vector<int> order(n);
std::iota(order.begin(), order.end(), 0);
std::stable_sort(order.begin(), order.end(),
[&](int i, int j) { return a[i] < a[j]; });
// Stable ties give sorted occurrence lists without per-value searches.
// Keep old xs alive until all reads finish, including build(xs).
std::vector<T> values;
values.reserve(n);
rk.resize(n);
occ.resize(n);
pos.clear();
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && !(a[order[i]] < a[order[j]]))
++j;
int id = int(values.size());
values.push_back(a[order[i]]);
pos.emplace_back(order.begin() + i, order.begin() + j);
for (int k = i; k < j; ++k) {
rk[order[k]] = id;
occ[order[k]] = k - i;
}
i = j;
}
xs = std::move(values);
md.assign(nb, std::vector<int>(nb, -1));
mc.assign(nb, std::vector<int>(nb));
std::vector<int> cnt(xs.size());
for (int lb = 0; lb < nb; ++lb) {
std::fill(cnt.begin(), cnt.end(), 0);
int best = -1, bc = 0;
for (int rb = lb; rb < nb; ++rb) {
int start = rb * bs, end = start + std::min(bs, n - start);
for (int i = start; i < end; ++i) {
int v = rk[i], count = ++cnt[v];
if (count > bc || (count == bc && v < best)) {
best = v;
bc = count;
}
}
md[lb][rb] = best;
mc[lb][rb] = bc;
}
}
}
/// @brief Return (mode, frequency), or nullopt for an empty range.
std::optional<std::pair<T, int>> query(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r)
return std::nullopt;
int off = l % bs, fl = l / bs + (off != 0), fr = r / bs;
int le = l + std::min(r - l, off ? bs - off : 0);
int rl = std::max(le, fr * bs);
int best = -1, bc = 0;
if (fl < fr) {
best = md[fl][fr - 1];
bc = mc[fl][fr - 1];
}
// The first left occurrence (last right occurrence) counts the whole
// range. Later repeats may undercount, but cannot improve its full count.
// The best frequency grows by at most the two boundary lengths in total.
for (int i = l; i < le; ++i) {
int v = rk[i], k = occ[i];
const auto &p = pos[v];
int remaining = int(p.size()) - k;
// Smaller values must also be considered when they only tie bc.
if (v < best && bc <= remaining && p[k + bc - 1] < r)
best = v;
while (bc < remaining && p[k + bc] < r) {
++bc;
best = v;
}
}
for (int i = r - 1; i >= rl; --i) {
int v = rk[i], k = occ[i];
const auto &p = pos[v];
if (v < best && bc <= k + 1 && p[k - bc + 1] >= l)
best = v;
while (bc <= k && p[k - bc] >= l) {
++bc;
best = v;
}
}
return std::pair<T, int>{xs[best], bc};
}
};
} // namespace noya
// NOYA_STATIC_RANGE_MODE_HPP
#ifndef NOYA_STATIC_RANGE_MODE_HPP
#define NOYA_STATIC_RANGE_MODE_HPP 1
/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n)) query.
/// Space: O(1+n), with O(1) value comparisons and copies.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static half-open range mode queries; ties return the smallest value.
/// Values use strict-weak-order equivalence. The array size fits int.
/// Construction owns its values; queries do not mutate shared scratch state.
template <class T> struct static_range_mode {
int n = 0;
int bs = 1;
int nb = 0;
std::vector<T> xs;
std::vector<int> rk;
std::vector<std::vector<int>> pos;
std::vector<std::vector<int>> md;
std::vector<int> occ;
std::vector<std::vector<int>> mc;
static_range_mode() = default;
explicit static_range_mode(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n = int(a.size());
bs = std::max(1, int(std::sqrt(std::max(1, n))));
nb = n / bs + (n % bs != 0);
std::vector<int> order(n);
std::iota(order.begin(), order.end(), 0);
std::stable_sort(order.begin(), order.end(),
[&](int i, int j) { return a[i] < a[j]; });
// Stable ties give sorted occurrence lists without per-value searches.
// Keep old xs alive until all reads finish, including build(xs).
std::vector<T> values;
values.reserve(n);
rk.resize(n);
occ.resize(n);
pos.clear();
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && !(a[order[i]] < a[order[j]]))
++j;
int id = int(values.size());
values.push_back(a[order[i]]);
pos.emplace_back(order.begin() + i, order.begin() + j);
for (int k = i; k < j; ++k) {
rk[order[k]] = id;
occ[order[k]] = k - i;
}
i = j;
}
xs = std::move(values);
md.assign(nb, std::vector<int>(nb, -1));
mc.assign(nb, std::vector<int>(nb));
std::vector<int> cnt(xs.size());
for (int lb = 0; lb < nb; ++lb) {
std::fill(cnt.begin(), cnt.end(), 0);
int best = -1, bc = 0;
for (int rb = lb; rb < nb; ++rb) {
int start = rb * bs, end = start + std::min(bs, n - start);
for (int i = start; i < end; ++i) {
int v = rk[i], count = ++cnt[v];
if (count > bc || (count == bc && v < best)) {
best = v;
bc = count;
}
}
md[lb][rb] = best;
mc[lb][rb] = bc;
}
}
}
/// @brief Return (mode, frequency), or nullopt for an empty range.
std::optional<std::pair<T, int>> query(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r)
return std::nullopt;
int off = l % bs, fl = l / bs + (off != 0), fr = r / bs;
int le = l + std::min(r - l, off ? bs - off : 0);
int rl = std::max(le, fr * bs);
int best = -1, bc = 0;
if (fl < fr) {
best = md[fl][fr - 1];
bc = mc[fl][fr - 1];
}
// The first left occurrence (last right occurrence) counts the whole
// range. Later repeats may undercount, but cannot improve its full count.
// The best frequency grows by at most the two boundary lengths in total.
for (int i = l; i < le; ++i) {
int v = rk[i], k = occ[i];
const auto &p = pos[v];
int remaining = int(p.size()) - k;
// Smaller values must also be considered when they only tie bc.
if (v < best && bc <= remaining && p[k + bc - 1] < r)
best = v;
while (bc < remaining && p[k + bc] < r) {
++bc;
best = v;
}
}
for (int i = r - 1; i >= rl; --i) {
int v = rk[i], k = occ[i];
const auto &p = pos[v];
if (v < best && bc <= k + 1 && p[k - bc + 1] >= l)
best = v;
while (bc <= k && p[k - bc] >= l) {
++bc;
best = v;
}
}
return std::pair<T, int>{xs[best], bc};
}
};
} // namespace noya
#endif // NOYA_STATIC_RANGE_MODE_HPP
/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n)) query.
/// Space: O(1+n), with O(1) value comparisons and copies.
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static half-open range mode queries; ties return the smallest value.
/// Values use strict-weak-order equivalence. The array size fits int.
/// Construction owns its values; queries do not mutate shared scratch state.
template <class T> struct static_range_mode {
int n = 0;
int bs = 1;
int nb = 0;
std::vector<T> xs;
std::vector<int> rk;
std::vector<std::vector<int>> pos;
std::vector<std::vector<int>> md;
std::vector<int> occ;
std::vector<std::vector<int>> mc;
static_range_mode() = default;
explicit static_range_mode(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
n = int(a.size());
bs = std::max(1, int(std::sqrt(std::max(1, n))));
nb = n / bs + (n % bs != 0);
std::vector<int> order(n);
std::iota(order.begin(), order.end(), 0);
std::stable_sort(order.begin(), order.end(),
[&](int i, int j) { return a[i] < a[j]; });
// Stable ties give sorted occurrence lists without per-value searches.
// Keep old xs alive until all reads finish, including build(xs).
std::vector<T> values;
values.reserve(n);
rk.resize(n);
occ.resize(n);
pos.clear();
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && !(a[order[i]] < a[order[j]]))
++j;
int id = int(values.size());
values.push_back(a[order[i]]);
pos.emplace_back(order.begin() + i, order.begin() + j);
for (int k = i; k < j; ++k) {
rk[order[k]] = id;
occ[order[k]] = k - i;
}
i = j;
}
xs = std::move(values);
md.assign(nb, std::vector<int>(nb, -1));
mc.assign(nb, std::vector<int>(nb));
std::vector<int> cnt(xs.size());
for (int lb = 0; lb < nb; ++lb) {
std::fill(cnt.begin(), cnt.end(), 0);
int best = -1, bc = 0;
for (int rb = lb; rb < nb; ++rb) {
int start = rb * bs, end = start + std::min(bs, n - start);
for (int i = start; i < end; ++i) {
int v = rk[i], count = ++cnt[v];
if (count > bc || (count == bc && v < best)) {
best = v;
bc = count;
}
}
md[lb][rb] = best;
mc[lb][rb] = bc;
}
}
}
/// @brief Return (mode, frequency), or nullopt for an empty range.
std::optional<std::pair<T, int>> query(int l, int r) const {
assert(0 <= l && l <= r && r <= n);
if (l == r)
return std::nullopt;
int off = l % bs, fl = l / bs + (off != 0), fr = r / bs;
int le = l + std::min(r - l, off ? bs - off : 0);
int rl = std::max(le, fr * bs);
int best = -1, bc = 0;
if (fl < fr) {
best = md[fl][fr - 1];
bc = mc[fl][fr - 1];
}
// The first left occurrence (last right occurrence) counts the whole
// range. Later repeats may undercount, but cannot improve its full count.
// The best frequency grows by at most the two boundary lengths in total.
for (int i = l; i < le; ++i) {
int v = rk[i], k = occ[i];
const auto &p = pos[v];
int remaining = int(p.size()) - k;
// Smaller values must also be considered when they only tie bc.
if (v < best && bc <= remaining && p[k + bc - 1] < r)
best = v;
while (bc < remaining && p[k + bc] < r) {
++bc;
best = v;
}
}
for (int i = r - 1; i >= rl; --i) {
int v = rk[i], k = occ[i];
const auto &p = pos[v];
if (v < best && bc <= k + 1 && p[k - bc + 1] >= l)
best = v;
while (bc <= k && p[k - bc] >= l) {
++bc;
best = v;
}
}
return std::pair<T, int>{xs[best], bc};
}
};
} // namespace noya
// NOYA_STATIC_RANGE_MODE_HPP