cp-library
競技プログラミング用 C++ ライブラリ
区間の異なる値の個数（クエリ一括処理）
data_structure/offline_range_count_distinct.hpp · GitHub で見る
共通ページ
#include "lib/data_structure/offline_range_count_distinct.hpp"
OfflineRangeCountDistinct<int> query(std::vector<int>{2, 1, 2, 3});
query.add_query(0, 3);
query.add_query(1, 4);
auto answer = query.solve(); // {2, 3}
| 操作 | 内容・返り値 |
|---|---|
OfflineRangeCountDistinct<T,Hash,Equal>(values) / build(values)
|
初期列を設定し、登録済みの問い合わせを消去 |
size() |
列の長さ |
reserve(q) |
問い合わせ数を予約 |
add_query(l,r) |
半開区間 [l,r) の問い合わせを追加し、答えの添字を返す |
solve() |
異なる値の個数を登録順の vector<int> で返す |
添字は 0 始まり、0 <= l <= r <= size() とします。空区間の答えは 0 です。solve() は登録内容を変更せず、繰り返し呼び出せます。入力配列は変更せず、構築後に破棄できます。T はコピー可能とし、Hash と Equal は std::unordered_map と同じ条件を満たすものを渡します。列長・問い合わせ数は INT_MAX 以下とします。
列長を \(N\)、問い合わせ数を \(Q\) とします。通常のハッシュ計算・比較を定数時間として、構築は \(O(N)\)、問い合わせの登録は償却 \(O(1)\)、solve() は期待 \(O((N+Q)\log N)\) 時間、空間は \(O(N+Q)\) です。
依存ライブラリ
コード
#ifndef OFFLINE_RANGE_COUNT_DISTINCT_HPP
#define OFFLINE_RANGE_COUNT_DISTINCT_HPP
#include "flat_hash_map.hpp"
#include "../components/incremental_prefix_count.hpp"
#include <array>
#include <cassert>
#include <functional>
#include <limits>
#include <vector>
template <class T, class Hash = std::hash<T>, class Equal = std::equal_to<T>>
class OfflineRangeCountDistinct {
std::vector<T> values;
std::vector<std::array<int, 2>> queries;
public:
OfflineRangeCountDistinct() = default;
explicit OfflineRangeCountDistinct(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
assert(a.size() <= std::size_t(std::numeric_limits<int>::max()));
values = a; queries.clear();
}
int size() const { return int(values.size()); }
void reserve(int count) { assert(count >= 0); queries.reserve(count); }
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= size() && queries.size() < std::size_t(std::numeric_limits<int>::max()));
queries.push_back({l, r});
return int(queries.size()) - 1;
}
std::vector<int> solve() const {
std::vector<int> result(queries.size());
if (queries.empty()) return result;
std::vector<int> ends(std::size_t(size()) + 2), order(queries.size());
for (auto query : queries) ++ends[std::size_t(query[1]) + 1];
for (std::size_t i = 1; i < ends.size(); ++i) ends[i] += ends[i - 1];
auto cursor = ends;
for (int i = 0; i < int(queries.size()); ++i) order[cursor[queries[i][1]]++] = i;
FlatHashMap<T, int, Hash, Equal> last;
last.reserve(values.size());
IncrementalPrefixCount positions(size());
for (std::size_t r = 0; r <= values.size(); ++r) {
if (r) {
int &previous = last[values[r - 1]];
positions.increment(previous);
previous = r;
}
for (int i = ends[r]; i < ends[r + 1]; ++i) {
int id = order[i];
int l = queries[id][0];
result[id] = std::size_t(l) == r ? 0 : positions.prefix(l + 1) - l;
}
}
return result;
}
};
#endif
#line 1 "data_structure/offline_range_count_distinct.hpp"
#line 1 "data_structure/flat_hash_map.hpp"
#include <algorithm>
#include <bit>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <memory>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>
namespace flat_hash_map_detail {
template<class K, class V, class Hash, class Equal>
inline constexpr bool packed = std::is_integral_v<K> && !std::is_same_v<K, bool> && sizeof(K) <= 8 &&
std::is_same_v<Hash, std::hash<K>> && std::is_same_v<Equal, std::equal_to<K>> &&
std::is_trivially_copyable_v<V> && std::is_nothrow_default_constructible_v<V> &&
std::is_nothrow_copy_constructible_v<V> && std::is_nothrow_copy_assignable_v<V>;
template<class K, class V, class Hash, class Equal, bool = packed<K, V, Hash, Equal>>
class Table {
std::unordered_map<K, V, Hash, Equal> values;
public:
Table() = default;
Table(const Table &) = default;
Table(Table &&other) : Table() { swap(other); }
Table &operator=(Table other) { swap(other); return *this; }
void swap(Table &other) noexcept(noexcept(values.swap(other.values))) { values.swap(other.values); }
std::size_t size() const { return values.size(); }
bool empty() const { return values.empty(); }
V *find(const K &key) { auto it = values.find(key); return it == values.end() ? nullptr : &it->second; }
const V *find(const K &key) const { auto it = values.find(key); return it == values.end() ? nullptr : &it->second; }
V &operator[](const K &key) { return values[key]; }
void set(const K &key, const V &value) { values.insert_or_assign(key, value); }
bool erase(const K &key) { return values.erase(key); }
void prefetch(const K &) const noexcept {}
void reserve(std::size_t n) { values.reserve(n); }
void clear() { values.clear(); }
};
template<class K, class V, class Hash, class Equal>
class Table<K, V, Hash, Equal, true> {
enum : unsigned char { vacant = 0, occupied = 1, tombstone = 2 };
struct Entry { K key{}; V value{}; };
struct ValueSlot { V value{}; };
static constexpr bool combined = sizeof(Entry) == sizeof(K) + sizeof(V) && sizeof(V) <= 16;
using Storage = std::conditional_t<combined, std::vector<Entry>, std::pair<std::vector<K>, std::vector<ValueSlot>>>;
Storage storage;
K &stored_key(std::size_t p) {
if constexpr (combined) return storage[p].key;
else return storage.first[p];
}
const K &stored_key(std::size_t p) const {
if constexpr (combined) return storage[p].key;
else return storage.first[p];
}
V &stored_value(std::size_t p) {
if constexpr (combined) return storage[p].value;
else return storage.second[p].value;
}
const V &stored_value(std::size_t p) const {
if constexpr (combined) return storage[p].value;
else return storage.second[p].value;
}
void resize(std::size_t capacity) {
if constexpr (combined) storage.resize(capacity);
else storage.first.resize(capacity), storage.second.resize(capacity);
}
std::size_t storage_limit() const {
if constexpr (combined) return storage.max_size();
else return std::min(storage.first.max_size(), storage.second.max_size());
}
std::vector<unsigned char> states;
std::size_t count = 0, deleted = 0;
unsigned shift = 64;
std::uint64_t salt = std::chrono::steady_clock::now().time_since_epoch().count();
std::size_t index(K key) const {
return ((static_cast<std::uint64_t>(key) ^ salt) * UINT64_C(11400714819323198485)) >> shift;
}
std::size_t locate(K key) const {
std::size_t p = index(key), mask = states.size() - 1;
while (states[p] != vacant && (states[p] != occupied || stored_key(p) != key)) p = (p + 1) & mask;
return p;
}
void rehash(std::size_t capacity) {
Table next;
next.salt = salt;
next.resize(capacity), next.states.resize(capacity);
next.shift = 64 - std::countr_zero(capacity);
for (std::size_t i = 0; i < states.size(); ++i) if (states[i] == occupied) {
std::size_t p = next.locate(stored_key(i));
next.stored_key(p) = stored_key(i), next.stored_value(p) = stored_value(i), next.states[p] = occupied;
}
next.count = count;
swap(next);
}
void prepare() {
if (states.empty()) rehash(16);
else if (count + deleted == states.size() / 2) {
if (deleted > count / 2) rehash(states.size());
else {
if (states.size() > states.max_size() / 2 || states.size() > storage_limit() / 2)
throw std::length_error("FlatHashMap capacity");
rehash(states.size() * 2);
}
}
}
std::size_t insert(K key) {
prepare();
std::size_t p = index(key), first = states.size(), mask = states.size() - 1;
while (states[p] != vacant) {
if (states[p] == occupied && stored_key(p) == key) return p;
if (states[p] == tombstone && first == states.size()) first = p;
p = (p + 1) & mask;
}
if (first != states.size()) p = first, --deleted;
stored_key(p) = key, stored_value(p) = V{}, states[p] = occupied;
++count;
return p;
}
public:
Table() = default;
Table(const Table &) = default;
Table(Table &&other) noexcept { swap(other); }
Table &operator=(Table other) noexcept { swap(other); return *this; }
void swap(Table &other) noexcept {
storage.swap(other.storage), states.swap(other.states);
std::swap(count, other.count), std::swap(deleted, other.deleted), std::swap(shift, other.shift), std::swap(salt, other.salt);
}
std::size_t size() const { return count; }
bool empty() const { return !count; }
V *find(K key) { if (states.empty()) return nullptr; std::size_t p = locate(key); return states[p] != vacant ? &stored_value(p) : nullptr; }
const V *find(K key) const { if (states.empty()) return nullptr; std::size_t p = locate(key); return states[p] != vacant ? &stored_value(p) : nullptr; }
V &operator[](K key) { return stored_value(insert(key)); }
void set(K key, const V &value) { V copy = value; stored_value(insert(key)) = copy; }
bool erase(K key) {
if (states.empty()) return false;
std::size_t p = locate(key);
if (states[p] == vacant) return false;
states[p] = tombstone, --count, ++deleted;
return true;
}
void prefetch(K key) const noexcept {
#if defined(__GNUC__) || defined(__clang__)
if (!states.empty()) {
std::size_t p = index(key);
__builtin_prefetch(states.data() + p, 0, 3);
__builtin_prefetch(std::addressof(stored_key(p)), 0, 3);
if constexpr (!combined) __builtin_prefetch(std::addressof(stored_value(p)), 0, 3);
}
#else
(void)key;
#endif
}
void reserve(std::size_t n) {
if (n <= states.size() / 2) return;
std::size_t limit = std::min(states.max_size(), storage_limit());
if (n > limit / 2) throw std::length_error("FlatHashMap capacity");
std::size_t capacity = std::bit_ceil(std::max(std::size_t(16), 2 * n));
if (capacity > limit) throw std::length_error("FlatHashMap capacity");
rehash(capacity);
}
void clear() { std::fill(states.begin(), states.end(), vacant); count = deleted = 0; }
};
}
template<class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
class FlatHashMap {
flat_hash_map_detail::Table<Key, T, Hash, KeyEqual> table;
public:
using key_type = Key;
using mapped_type = T;
using size_type = std::size_t;
FlatHashMap() = default;
explicit FlatHashMap(size_type n) { reserve(n); }
bool empty() const { return table.empty(); }
size_type size() const { return table.size(); }
T *find(const Key &key) { return table.find(key); }
const T *find(const Key &key) const { return table.find(key); }
bool contains(const Key &key) const { return find(key) != nullptr; }
size_type count(const Key &key) const { return contains(key); }
std::optional<T> get(const Key &key) const { const T *p = find(key); return p ? std::optional<T>(*p) : std::nullopt; }
T &at(const Key &key) { T *p = find(key); if (!p) throw std::out_of_range("FlatHashMap key"); return *p; }
const T &at(const Key &key) const { const T *p = find(key); if (!p) throw std::out_of_range("FlatHashMap key"); return *p; }
T &operator[](const Key &key) { return table[key]; }
void set(const Key &key, const T &value) { table.set(key, value); }
bool erase(const Key &key) { return table.erase(key); }
void prefetch(const Key &key) const noexcept { table.prefetch(key); }
void reserve(size_type n) { table.reserve(n); }
void clear() { table.clear(); }
void swap(FlatHashMap &other) noexcept(noexcept(table.swap(other.table))) { table.swap(other.table); }
friend void swap(FlatHashMap &a, FlatHashMap &b) noexcept(noexcept(a.swap(b))) { a.swap(b); }
};
#line 1 "components/incremental_prefix_count.hpp"
#include <array>
#include <cassert>
#line 10 "components/incremental_prefix_count.hpp"
#if defined(__x86_64__) || defined(__i386__)
#include <immintrin.h>
#endif
class IncrementalPrefixCount {
std::vector<std::vector<std::array<std::uint32_t, 16>>> levels;
int n = 0, total = 0;
[[maybe_unused]] bool vectorized = false;
static void add_scalar(std::uint32_t *values, int first) {
for (int i = first; i < 16; ++i) ++values[i];
}
#if defined(__x86_64__) || defined(__i386__)
__attribute__((target("avx2"), always_inline)) static void add_avx2(std::uint32_t *values, int first) {
if (first == 16) return;
int i = first & ~7;
auto active = _mm256_cmpgt_epi32(_mm256_setr_epi32(i, i + 1, i + 2, i + 3, i + 4, i + 5, i + 6, i + 7), _mm256_set1_epi32(first - 1));
auto p = reinterpret_cast<__m256i *>(values + i);
_mm256_storeu_si256(p, _mm256_sub_epi32(_mm256_loadu_si256(p), active));
if (!i) {
p = reinterpret_cast<__m256i *>(values + 8);
_mm256_storeu_si256(p, _mm256_add_epi32(_mm256_loadu_si256(p), _mm256_set1_epi32(1)));
}
}
__attribute__((target("avx2"))) void increment_avx2(std::size_t p) {
add_avx2(levels[0][p >> 4].data(), p & 15);
for (unsigned level = 1; level < levels.size(); ++level)
add_avx2(levels[level][p >> (4 * (level + 1))].data(), ((p >> (4 * level)) & 15) + 1);
}
#endif
public:
explicit IncrementalPrefixCount(int size = 0) : n(size) {
assert(size >= 0);
for (std::size_t width = std::size_t(size); width > 1 || levels.empty();) {
width = (width + 15) >> 4;
levels.emplace_back(width);
}
#if defined(__x86_64__) || defined(__i386__)
vectorized = __builtin_cpu_supports("avx2");
#endif
}
int size() const { return n; }
void increment(int p) {
assert(0 <= p && p < n && total < std::numeric_limits<int>::max());
++total;
#if defined(__x86_64__) || defined(__i386__)
if (vectorized) { increment_avx2(unsigned(p)); return; }
#endif
std::size_t index = unsigned(p);
add_scalar(levels[0][index >> 4].data(), index & 15);
for (unsigned level = 1; level < levels.size(); ++level)
add_scalar(levels[level][index >> (4 * (level + 1))].data(), ((index >> (4 * level)) & 15) + 1);
}
int prefix(int r) const {
assert(0 <= r && r <= n);
if (!r) return 0;
std::size_t p = unsigned(r - 1);
std::uint32_t result = levels[0][p >> 4][p & 15];
for (unsigned level = 1; level < levels.size(); ++level) result += levels[level][p >> (4 * (level + 1))][(p >> (4 * level)) & 15];
return int(result);
}
};
#line 11 "data_structure/offline_range_count_distinct.hpp"
template <class T, class Hash = std::hash<T>, class Equal = std::equal_to<T>>
class OfflineRangeCountDistinct {
std::vector<T> values;
std::vector<std::array<int, 2>> queries;
public:
OfflineRangeCountDistinct() = default;
explicit OfflineRangeCountDistinct(const std::vector<T> &a) { build(a); }
void build(const std::vector<T> &a) {
assert(a.size() <= std::size_t(std::numeric_limits<int>::max()));
values = a; queries.clear();
}
int size() const { return int(values.size()); }
void reserve(int count) { assert(count >= 0); queries.reserve(count); }
int add_query(int l, int r) {
assert(0 <= l && l <= r && r <= size() && queries.size() < std::size_t(std::numeric_limits<int>::max()));
queries.push_back({l, r});
return int(queries.size()) - 1;
}
std::vector<int> solve() const {
std::vector<int> result(queries.size());
if (queries.empty()) return result;
std::vector<int> ends(std::size_t(size()) + 2), order(queries.size());
for (auto query : queries) ++ends[std::size_t(query[1]) + 1];
for (std::size_t i = 1; i < ends.size(); ++i) ends[i] += ends[i - 1];
auto cursor = ends;
for (int i = 0; i < int(queries.size()); ++i) order[cursor[queries[i][1]]++] = i;
FlatHashMap<T, int, Hash, Equal> last;
last.reserve(values.size());
IncrementalPrefixCount positions(size());
for (std::size_t r = 0; r <= values.size(); ++r) {
if (r) {
int &previous = last[values[r - 1]];
positions.increment(previous);
previous = r;
}
for (int i = ends[r]; i < ends[r + 1]; ++i) {
int id = order[i];
int l = queries[id][0];
result[id] = std::size_t(l) == r ? 0 : positions.prefix(l + 1) - l;
}
}
return result;
}
};