static_range_mode.hpp¶
Static half-open range mode queries in O(sqrt(n) log n), with O(n sqrt(n)) preprocessing; ties return the smallest value.
Verified by static_range_mode_query.
预处理静态数组的区间众数查询，返回出现次数最多的值及频次。
Implementation¶
#ifndef NOYA_STATIC_RANGE_MODE_HPP
#define NOYA_STATIC_RANGE_MODE_HPP 1
/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n) log n) query.
/// Space: O(n sqrt(n)).
#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Static half-open range mode queries in O(sqrt(n) log n), with
/// O(n sqrt(n)) preprocessing; ties return the smallest value.
template <class T> struct static_range_mode {
int n = 0;
int block_size = 1;
int block_count = 0;
std::vector<T> coordinates;
std::vector<int> rank;
std::vector<std::vector<int>> positions;
std::vector<std::vector<int>> block_mode;
static_range_mode() = default;
explicit static_range_mode(const std::vector<T> &values) { build(values); }
void build(const std::vector<T> &values) {
n = int(values.size());
block_size = std::max(1, int(std::sqrt(std::max(1, n))));
block_count = (n + block_size - 1) / block_size;
coordinates = values;
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
rank.resize(n);
positions.assign(coordinates.size(), {});
for (int index = 0; index < n; index++) {
rank[index] = int(std::lower_bound(coordinates.begin(), coordinates.end(),
values[index]) -
coordinates.begin());
positions[rank[index]].push_back(index);
}
block_mode.assign(block_count, std::vector<int>(block_count, -1));
std::vector<int> frequency(coordinates.size());
for (int left_block = 0; left_block < block_count; left_block++) {
std::fill(frequency.begin(), frequency.end(), 0);
int best = -1;
for (int index = left_block * block_size; index < n; index++) {
int value = rank[index];
frequency[value]++;
if (best == -1 || frequency[value] > frequency[best] ||
(frequency[value] == frequency[best] && value < best)) {
best = value;
}
int right_block = index / block_size;
block_mode[left_block][right_block] = best;
}
}
}
/// @brief Return (mode, frequency), or nullopt for an empty range.
std::optional<std::pair<T, int>> query(int left, int right) const {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return std::nullopt;
}
int first_full = (left + block_size - 1) / block_size;
int last_full = right / block_size;
std::vector<int> candidates;
if (first_full < last_full) {
candidates.push_back(block_mode[first_full][last_full - 1]);
}
int left_fringe_end = std::min(right, first_full * block_size);
for (int index = left; index < left_fringe_end; index++) {
candidates.push_back(rank[index]);
}
int right_fringe_begin = std::max(left_fringe_end, last_full * block_size);
for (int index = right_fringe_begin; index < right; index++) {
candidates.push_back(rank[index]);
}
std::sort(candidates.begin(), candidates.end());
candidates.erase(std::unique(candidates.begin(), candidates.end()),
candidates.end());
int best = candidates[0];
int best_frequency = -1;
for (int candidate : candidates) {
const auto &list = positions[candidate];
int frequency = int(std::lower_bound(list.begin(), list.end(), right) -
std::lower_bound(list.begin(), list.end(), left));
if (frequency > best_frequency ||
(frequency == best_frequency && candidate < best)) {
best = candidate;
best_frequency = frequency;
}
}
return std::pair<T, int>{coordinates[best], best_frequency};
}
};
} // namespace noya
#endif // NOYA_STATIC_RANGE_MODE_HPP
#include <algorithm>
#include <cassert>
#include <cmath>
#include <optional>
#include <utility>
#include <vector>
/// @complexity Time: O(n sqrt(n)) build and O(sqrt(n) log n) query.
/// Space: O(n sqrt(n)).
namespace noya {
/// @brief Static half-open range mode queries in O(sqrt(n) log n), with
/// O(n sqrt(n)) preprocessing; ties return the smallest value.
template <class T> struct static_range_mode {
int n = 0;
int block_size = 1;
int block_count = 0;
std::vector<T> coordinates;
std::vector<int> rank;
std::vector<std::vector<int>> positions;
std::vector<std::vector<int>> block_mode;
static_range_mode() = default;
explicit static_range_mode(const std::vector<T> &values) { build(values); }
void build(const std::vector<T> &values) {
n = int(values.size());
block_size = std::max(1, int(std::sqrt(std::max(1, n))));
block_count = (n + block_size - 1) / block_size;
coordinates = values;
std::sort(coordinates.begin(), coordinates.end());
coordinates.erase(std::unique(coordinates.begin(), coordinates.end()),
coordinates.end());
rank.resize(n);
positions.assign(coordinates.size(), {});
for (int index = 0; index < n; index++) {
rank[index] = int(std::lower_bound(coordinates.begin(), coordinates.end(),
values[index]) -
coordinates.begin());
positions[rank[index]].push_back(index);
}
block_mode.assign(block_count, std::vector<int>(block_count, -1));
std::vector<int> frequency(coordinates.size());
for (int left_block = 0; left_block < block_count; left_block++) {
std::fill(frequency.begin(), frequency.end(), 0);
int best = -1;
for (int index = left_block * block_size; index < n; index++) {
int value = rank[index];
frequency[value]++;
if (best == -1 || frequency[value] > frequency[best] ||
(frequency[value] == frequency[best] && value < best)) {
best = value;
}
int right_block = index / block_size;
block_mode[left_block][right_block] = best;
}
}
}
/// @brief Return (mode, frequency), or nullopt for an empty range.
std::optional<std::pair<T, int>> query(int left, int right) const {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return std::nullopt;
}
int first_full = (left + block_size - 1) / block_size;
int last_full = right / block_size;
std::vector<int> candidates;
if (first_full < last_full) {
candidates.push_back(block_mode[first_full][last_full - 1]);
}
int left_fringe_end = std::min(right, first_full * block_size);
for (int index = left; index < left_fringe_end; index++) {
candidates.push_back(rank[index]);
}
int right_fringe_begin = std::max(left_fringe_end, last_full * block_size);
for (int index = right_fringe_begin; index < right; index++) {
candidates.push_back(rank[index]);
}
std::sort(candidates.begin(), candidates.end());
candidates.erase(std::unique(candidates.begin(), candidates.end()),
candidates.end());
int best = candidates[0];
int best_frequency = -1;
for (int candidate : candidates) {
const auto &list = positions[candidate];
int frequency = int(std::lower_bound(list.begin(), list.end(), right) -
std::lower_bound(list.begin(), list.end(), left));
if (frequency > best_frequency ||
(frequency == best_frequency && candidate < best)) {
best = candidate;
best_frequency = frequency;
}
}
return std::pair<T, int>{coordinates[best], best_frequency};
}
};
} // namespace noya