point_set_range_freq.hpp¶
维护数组的单点赋值，并统计区间内某个值的出现次数；适合动态序列上的区间频率查询。
Complexity: Time: \(O(n \log (d + 1))\) build for \(d\) distinct input values; expected \(O(\log n)\) assignment/frequency query. Space: \(O(n)\), including \(O(n)\) temporary build workspace.
AC 记录：point_set_range_frequency。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log(d+1)) build for d distinct input values;
/// expected O(log n) assignment/frequency query. Space: O(n), including
/// O(n) temporary build workspace.
#include <cassert>
#include <cstdint>
#include <map>
#include <random>
#include <utility>
#include <vector>
namespace noya {
/// @brief Point assignment and exact-value frequency queries on half-open
/// ranges, both in expected O(log n) time.
template <class T> struct point_set_range_frequency {
struct node {
int ls = -1;
int rs = -1;
int sz = 1;
std::uint64_t rnd = 0;
};
int n = 0;
std::vector<T> a;
std::vector<node> tr;
std::map<T, int> rt;
point_set_range_frequency() = default;
explicit point_set_range_frequency(
const std::vector<T> &arr, std::uint64_t rng = 0x243f6a8885a308d3ULL) {
build(arr, rng);
}
/// @brief Rebuild in O(n log(d+1)) time for d distinct input values.
void build(const std::vector<T> &arr,
std::uint64_t rng = 0x243f6a8885a308d3ULL) {
n = int(arr.size());
a = arr;
tr.assign(n, {});
rt.clear();
std::mt19937_64 rd(rng);
std::vector<int> parent(n, -1);
for (int idx = 0; idx < n; idx++) {
tr[idx].rnd = rd();
auto [it, ok] = rt.try_emplace(a[idx], -1);
// During construction each map entry holds its right-spine stack top.
int top = it->second, last = -1;
while (top != -1 && higher_priority(idx, top)) {
last = top;
pull(top);
top = parent[top];
}
tr[idx].ls = last;
if (top != -1) {
tr[top].rs = idx;
}
parent[idx] = top;
it->second = idx;
}
for (auto &[val, top] : rt) {
while (parent[top] != -1) {
pull(top);
top = parent[top];
}
pull(top);
}
}
/// @brief Assign value to position index in expected O(log n) time.
void set(int idx, const T &val) {
assert(0 <= idx && idx < n);
if (a[idx] == val) {
return;
}
auto oit = rt.find(a[idx]);
assert(oit != rt.end());
oit->second = erase(oit->second, idx);
if (oit->second == -1) {
rt.erase(oit);
}
tr[idx].ls = tr[idx].rs = -1;
tr[idx].sz = 1;
auto [nit, ok] = rt.try_emplace(val, -1);
nit->second = insert(nit->second, idx);
a[idx] = val;
}
/// @brief Count occurrences of value in [l, r) in expected O(log n)
/// time.
int query(int l, int r, const T &val) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return 0;
}
auto it = rt.find(val);
if (it == rt.end()) {
return 0;
}
int root = it->second;
// Skip the shared part of the two prefix searches only once.
while (root != -1) {
if (root < l) {
root = tr[root].rs;
} else if (root >= r) {
root = tr[root].ls;
} else {
return 1 + subtree_size(tr[root].ls) - count_less(tr[root].ls, l) +
count_less(tr[root].rs, r);
}
}
return 0;
}
/// @brief Return the current value at one position.
const T &get(int idx) const {
assert(0 <= idx && idx < n);
return a[idx];
}
private:
int subtree_size(int rt0) const { return rt0 == -1 ? 0 : tr[rt0].sz; }
void pull(int rt0) {
tr[rt0].sz = 1 + subtree_size(tr[rt0].ls) + subtree_size(tr[rt0].rs);
}
bool higher_priority(int A, int b) const {
return tr[A].rnd != tr[b].rnd ? tr[A].rnd > tr[b].rnd : A < b;
}
std::pair<int, int> split(int rt0, int key) {
if (rt0 == -1) {
return {-1, -1};
}
if (rt0 < key) {
auto [l, r] = split(tr[rt0].rs, key);
tr[rt0].rs = l;
pull(rt0);
return {rt0, r};
}
auto [l, r] = split(tr[rt0].ls, key);
tr[rt0].ls = r;
pull(rt0);
return {l, rt0};
}
int merge(int l, int r) {
if (l == -1) {
return r;
}
if (r == -1) {
return l;
}
if (higher_priority(l, r)) {
tr[l].rs = merge(tr[l].rs, r);
pull(l);
return l;
}
tr[r].ls = merge(l, tr[r].ls);
pull(r);
return r;
}
int insert(int rt0, int idx) {
if (rt0 == -1) {
return idx;
}
if (higher_priority(idx, rt0)) {
auto [l, r] = split(rt0, idx);
tr[idx].ls = l;
tr[idx].rs = r;
pull(idx);
return idx;
}
if (idx < rt0) {
tr[rt0].ls = insert(tr[rt0].ls, idx);
} else {
tr[rt0].rs = insert(tr[rt0].rs, idx);
}
pull(rt0);
return rt0;
}
int erase(int rt0, int idx) {
assert(rt0 != -1);
if (rt0 == idx) {
return merge(tr[rt0].ls, tr[rt0].rs);
}
if (idx < rt0) {
tr[rt0].ls = erase(tr[rt0].ls, idx);
} else {
tr[rt0].rs = erase(tr[rt0].rs, idx);
}
pull(rt0);
return rt0;
}
int count_less(int rt0, int key) const {
int res = 0;
while (rt0 != -1) {
if (rt0 < key) {
res += 1 + subtree_size(tr[rt0].ls);
rt0 = tr[rt0].rs;
} else {
rt0 = tr[rt0].ls;
}
}
return res;
}
};
} // namespace noya
// NOYA_POINT_SET_RANGE_FREQUENCY_HPP
#ifndef NOYA_POINT_SET_RANGE_FREQUENCY_HPP
#define NOYA_POINT_SET_RANGE_FREQUENCY_HPP 1
/// @complexity Time: O(n log(d+1)) build for d distinct input values;
/// expected O(log n) assignment/frequency query. Space: O(n), including
/// O(n) temporary build workspace.
#include <cassert>
#include <cstdint>
#include <map>
#include <random>
#include <utility>
#include <vector>
namespace noya {
/// @brief Point assignment and exact-value frequency queries on half-open
/// ranges, both in expected O(log n) time.
template <class T> struct point_set_range_frequency {
struct node {
int ls = -1;
int rs = -1;
int sz = 1;
std::uint64_t rnd = 0;
};
int n = 0;
std::vector<T> a;
std::vector<node> tr;
std::map<T, int> rt;
point_set_range_frequency() = default;
explicit point_set_range_frequency(
const std::vector<T> &arr, std::uint64_t rng = 0x243f6a8885a308d3ULL) {
build(arr, rng);
}
/// @brief Rebuild in O(n log(d+1)) time for d distinct input values.
void build(const std::vector<T> &arr,
std::uint64_t rng = 0x243f6a8885a308d3ULL) {
n = int(arr.size());
a = arr;
tr.assign(n, {});
rt.clear();
std::mt19937_64 rd(rng);
std::vector<int> parent(n, -1);
for (int idx = 0; idx < n; idx++) {
tr[idx].rnd = rd();
auto [it, ok] = rt.try_emplace(a[idx], -1);
// During construction each map entry holds its right-spine stack top.
int top = it->second, last = -1;
while (top != -1 && higher_priority(idx, top)) {
last = top;
pull(top);
top = parent[top];
}
tr[idx].ls = last;
if (top != -1) {
tr[top].rs = idx;
}
parent[idx] = top;
it->second = idx;
}
for (auto &[val, top] : rt) {
while (parent[top] != -1) {
pull(top);
top = parent[top];
}
pull(top);
}
}
/// @brief Assign value to position index in expected O(log n) time.
void set(int idx, const T &val) {
assert(0 <= idx && idx < n);
if (a[idx] == val) {
return;
}
auto oit = rt.find(a[idx]);
assert(oit != rt.end());
oit->second = erase(oit->second, idx);
if (oit->second == -1) {
rt.erase(oit);
}
tr[idx].ls = tr[idx].rs = -1;
tr[idx].sz = 1;
auto [nit, ok] = rt.try_emplace(val, -1);
nit->second = insert(nit->second, idx);
a[idx] = val;
}
/// @brief Count occurrences of value in [l, r) in expected O(log n)
/// time.
int query(int l, int r, const T &val) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return 0;
}
auto it = rt.find(val);
if (it == rt.end()) {
return 0;
}
int root = it->second;
// Skip the shared part of the two prefix searches only once.
while (root != -1) {
if (root < l) {
root = tr[root].rs;
} else if (root >= r) {
root = tr[root].ls;
} else {
return 1 + subtree_size(tr[root].ls) - count_less(tr[root].ls, l) +
count_less(tr[root].rs, r);
}
}
return 0;
}
/// @brief Return the current value at one position.
const T &get(int idx) const {
assert(0 <= idx && idx < n);
return a[idx];
}
private:
int subtree_size(int rt0) const { return rt0 == -1 ? 0 : tr[rt0].sz; }
void pull(int rt0) {
tr[rt0].sz = 1 + subtree_size(tr[rt0].ls) + subtree_size(tr[rt0].rs);
}
bool higher_priority(int A, int b) const {
return tr[A].rnd != tr[b].rnd ? tr[A].rnd > tr[b].rnd : A < b;
}
std::pair<int, int> split(int rt0, int key) {
if (rt0 == -1) {
return {-1, -1};
}
if (rt0 < key) {
auto [l, r] = split(tr[rt0].rs, key);
tr[rt0].rs = l;
pull(rt0);
return {rt0, r};
}
auto [l, r] = split(tr[rt0].ls, key);
tr[rt0].ls = r;
pull(rt0);
return {l, rt0};
}
int merge(int l, int r) {
if (l == -1) {
return r;
}
if (r == -1) {
return l;
}
if (higher_priority(l, r)) {
tr[l].rs = merge(tr[l].rs, r);
pull(l);
return l;
}
tr[r].ls = merge(l, tr[r].ls);
pull(r);
return r;
}
int insert(int rt0, int idx) {
if (rt0 == -1) {
return idx;
}
if (higher_priority(idx, rt0)) {
auto [l, r] = split(rt0, idx);
tr[idx].ls = l;
tr[idx].rs = r;
pull(idx);
return idx;
}
if (idx < rt0) {
tr[rt0].ls = insert(tr[rt0].ls, idx);
} else {
tr[rt0].rs = insert(tr[rt0].rs, idx);
}
pull(rt0);
return rt0;
}
int erase(int rt0, int idx) {
assert(rt0 != -1);
if (rt0 == idx) {
return merge(tr[rt0].ls, tr[rt0].rs);
}
if (idx < rt0) {
tr[rt0].ls = erase(tr[rt0].ls, idx);
} else {
tr[rt0].rs = erase(tr[rt0].rs, idx);
}
pull(rt0);
return rt0;
}
int count_less(int rt0, int key) const {
int res = 0;
while (rt0 != -1) {
if (rt0 < key) {
res += 1 + subtree_size(tr[rt0].ls);
rt0 = tr[rt0].rs;
} else {
rt0 = tr[rt0].ls;
}
}
return res;
}
};
} // namespace noya
#endif // NOYA_POINT_SET_RANGE_FREQUENCY_HPP
/// @complexity Time: O(n log(d+1)) build for d distinct input values;
/// expected O(log n) assignment/frequency query. Space: O(n), including
/// O(n) temporary build workspace.
#include <cassert>
#include <cstdint>
#include <map>
#include <random>
#include <utility>
#include <vector>
namespace noya {
/// @brief Point assignment and exact-value frequency queries on half-open
/// ranges, both in expected O(log n) time.
template <class T> struct point_set_range_frequency {
struct node {
int ls = -1;
int rs = -1;
int sz = 1;
std::uint64_t rnd = 0;
};
int n = 0;
std::vector<T> a;
std::vector<node> tr;
std::map<T, int> rt;
point_set_range_frequency() = default;
explicit point_set_range_frequency(
const std::vector<T> &arr, std::uint64_t rng = 0x243f6a8885a308d3ULL) {
build(arr, rng);
}
/// @brief Rebuild in O(n log(d+1)) time for d distinct input values.
void build(const std::vector<T> &arr,
std::uint64_t rng = 0x243f6a8885a308d3ULL) {
n = int(arr.size());
a = arr;
tr.assign(n, {});
rt.clear();
std::mt19937_64 rd(rng);
std::vector<int> parent(n, -1);
for (int idx = 0; idx < n; idx++) {
tr[idx].rnd = rd();
auto [it, ok] = rt.try_emplace(a[idx], -1);
// During construction each map entry holds its right-spine stack top.
int top = it->second, last = -1;
while (top != -1 && higher_priority(idx, top)) {
last = top;
pull(top);
top = parent[top];
}
tr[idx].ls = last;
if (top != -1) {
tr[top].rs = idx;
}
parent[idx] = top;
it->second = idx;
}
for (auto &[val, top] : rt) {
while (parent[top] != -1) {
pull(top);
top = parent[top];
}
pull(top);
}
}
/// @brief Assign value to position index in expected O(log n) time.
void set(int idx, const T &val) {
assert(0 <= idx && idx < n);
if (a[idx] == val) {
return;
}
auto oit = rt.find(a[idx]);
assert(oit != rt.end());
oit->second = erase(oit->second, idx);
if (oit->second == -1) {
rt.erase(oit);
}
tr[idx].ls = tr[idx].rs = -1;
tr[idx].sz = 1;
auto [nit, ok] = rt.try_emplace(val, -1);
nit->second = insert(nit->second, idx);
a[idx] = val;
}
/// @brief Count occurrences of value in [l, r) in expected O(log n)
/// time.
int query(int l, int r, const T &val) const {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return 0;
}
auto it = rt.find(val);
if (it == rt.end()) {
return 0;
}
int root = it->second;
// Skip the shared part of the two prefix searches only once.
while (root != -1) {
if (root < l) {
root = tr[root].rs;
} else if (root >= r) {
root = tr[root].ls;
} else {
return 1 + subtree_size(tr[root].ls) - count_less(tr[root].ls, l) +
count_less(tr[root].rs, r);
}
}
return 0;
}
/// @brief Return the current value at one position.
const T &get(int idx) const {
assert(0 <= idx && idx < n);
return a[idx];
}
private:
int subtree_size(int rt0) const { return rt0 == -1 ? 0 : tr[rt0].sz; }
void pull(int rt0) {
tr[rt0].sz = 1 + subtree_size(tr[rt0].ls) + subtree_size(tr[rt0].rs);
}
bool higher_priority(int A, int b) const {
return tr[A].rnd != tr[b].rnd ? tr[A].rnd > tr[b].rnd : A < b;
}
std::pair<int, int> split(int rt0, int key) {
if (rt0 == -1) {
return {-1, -1};
}
if (rt0 < key) {
auto [l, r] = split(tr[rt0].rs, key);
tr[rt0].rs = l;
pull(rt0);
return {rt0, r};
}
auto [l, r] = split(tr[rt0].ls, key);
tr[rt0].ls = r;
pull(rt0);
return {l, rt0};
}
int merge(int l, int r) {
if (l == -1) {
return r;
}
if (r == -1) {
return l;
}
if (higher_priority(l, r)) {
tr[l].rs = merge(tr[l].rs, r);
pull(l);
return l;
}
tr[r].ls = merge(l, tr[r].ls);
pull(r);
return r;
}
int insert(int rt0, int idx) {
if (rt0 == -1) {
return idx;
}
if (higher_priority(idx, rt0)) {
auto [l, r] = split(rt0, idx);
tr[idx].ls = l;
tr[idx].rs = r;
pull(idx);
return idx;
}
if (idx < rt0) {
tr[rt0].ls = insert(tr[rt0].ls, idx);
} else {
tr[rt0].rs = insert(tr[rt0].rs, idx);
}
pull(rt0);
return rt0;
}
int erase(int rt0, int idx) {
assert(rt0 != -1);
if (rt0 == idx) {
return merge(tr[rt0].ls, tr[rt0].rs);
}
if (idx < rt0) {
tr[rt0].ls = erase(tr[rt0].ls, idx);
} else {
tr[rt0].rs = erase(tr[rt0].rs, idx);
}
pull(rt0);
return rt0;
}
int count_less(int rt0, int key) const {
int res = 0;
while (rt0 != -1) {
if (rt0 < key) {
res += 1 + subtree_size(tr[rt0].ls);
rt0 = tr[rt0].rs;
} else {
rt0 = tr[rt0].ls;
}
}
return res;
}
};
} // namespace noya
// NOYA_POINT_SET_RANGE_FREQUENCY_HPP