cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
Dynamic Rolling Hash
(library/string/dynamic_rolling_hash.hpp)
- View this file on GitHub
- Last update: 2023-01-08 05:15:03+09:00
- Include:
#include "library/string/dynamic_rolling_hash.hpp"
Dynamic Rolling Hash
Depends on
区間和取得が可能な赤黒木
(library/datastructure/bbst/red_black_segment_tree.hpp)
- Red Black Tree Base
(library/datastructure/bbst/red_black_tree_base.hpp)
- Internal Eratosthenes
(library/number/internal_eratosthenes.hpp)
- Modint 2^61m1
(library/number/modint_2^61m1.hpp)
- エラトステネスの篩
(library/number/sieve_of_eratosthenes.hpp)
- Object Pool
(library/util/object_pool.hpp)
Code
#ifndef SUISEN_DYNAMIC_ROLLING_HASH
#define SUISEN_DYNAMIC_ROLLING_HASH
#include <random>
#include "library/number/sieve_of_eratosthenes.hpp"
#include "library/number/modint_2^61m1.hpp"
#include "library/datastructure/bbst/red_black_segment_tree.hpp"
namespace suisen {
namespace internal::dynamic_rolling_hash {
struct BaseGen {
static inline std::mt19937_64 rng{ std::random_device{}() };
static inline std::uniform_int_distribution<uint64_t> dist{ 0, modint2p61m1::mod() - 1 };
static uint32_t generate() {
return dist(rng);
}
};
template <size_t id>
uint32_t base() {
static uint32_t _base = 0;
return _base ? _base : (_base = BaseGen::generate());
}
template <size_t base_num_>
struct Hash {
static constexpr size_t base_num = base_num_;
using child_type = Hash<base_num - 1>;
using hash_type = std::array<uint64_t, base_num>;
modint2p61m1 hash;
modint2p61m1 offset;
child_type hash_lo;
Hash() : Hash(0) {}
template <typename T>
Hash(const T& val): hash(val), offset(base<base_num>()), hash_lo(val) {}
operator hash_type() const {
hash_type res;
store_hash(res);
return res;
}
template <typename Container>
void store_hash(Container& h) const {
h[base_num - 1] = hash.val();
hash_lo.store_hash(h);
}
static Hash identity() {
return { 0, 1, child_type::identity() };
}
static Hash merge(const Hash &l, const Hash &r) {
return { l.hash * r.offset + r.hash, l.offset * r.offset, child_type::merge(l.hash_lo, r.hash_lo) };
}
static Hash merge_noref(Hash l, Hash r) {
return merge(l, r);
}
private:
Hash(const modint2p61m1& hash, const modint2p61m1& offset, const child_type& hash_lo): hash(hash), offset(offset), hash_lo(hash_lo) {}
};
template <>
struct Hash<1> {
static constexpr size_t base_num = 1;
modint2p61m1 hash;
modint2p61m1 offset;
using hash_type = uint64_t;
Hash() : Hash(0) {}
template <typename T>
Hash(const T& val): hash(val), offset(base<base_num>()) {}
operator hash_type() const {
return hash.val();
}
template <typename Container>
void store_hash(Container& h) const {
h[0] = hash.val();
}
static Hash identity() {
return { 0, 1 };
}
static Hash merge(const Hash &l, const Hash &r) {
return { l.hash * r.offset + r.hash, l.offset * r.offset };
}
static Hash merge_noref(Hash l, Hash r) {
return merge(l, r);
}
private:
Hash(const modint2p61m1& hash, const modint2p61m1& offset): hash(hash), offset(offset) {}
};
}
template <std::size_t base_num>
using Hash = internal::dynamic_rolling_hash::Hash<base_num>;
template <size_t base_num_ = 1>
struct DynamicRollingHash {
static constexpr size_t base_num = base_num_;
private:
using hash_ = Hash<base_num>;
using node = bbst::segtree::RedBlackTreeNode<hash_, hash_::merge_noref, hash_::identity>;
node* _seq;
public:
using hash = typename hash_::hash_type;
DynamicRollingHash(): _seq(nullptr) {}
template <typename Seq>
DynamicRollingHash(const Seq& a): _seq(node::build(a)) {}
static void init_pool(size_t reserving_node_num) {
node::init_pool(reserving_node_num);
}
template <typename T>
void set(size_t k, const T& val) {
_seq = node::update_value(_seq, k, val);
}
template <typename T>
void insert(size_t k, const T& val) {
_seq = node::insert(_seq, k, val);
}
template <typename T>
void push_back(const T& val) {
insert(node::size(_seq), val);
}
template <typename T>
void push_front(const T& val) {
insert(0, val);
}
void erase(size_t k) {
_seq = node::erase(_seq, k).first;
}
void pop_back() {
erase(node::size(_seq) - 1);
}
void pop_front() {
erase(0);
}
hash operator()(int l, int r) {
hash_ res;
std::tie(_seq, res) = node::prod(_seq, l, r);
return res;
}
};
}
#endif // SUISEN_DYNAMIC_ROLLING_HASH#line 1 "library/string/dynamic_rolling_hash.hpp"
#include <random>
#line 1 "library/number/sieve_of_eratosthenes.hpp"
#include <cassert>
#include <cmath>
#include <vector>
#line 1 "library/number/internal_eratosthenes.hpp"
#include <cstdint>
#line 6 "library/number/internal_eratosthenes.hpp"
namespace suisen::internal::sieve {
constexpr std::uint8_t K = 8;
constexpr std::uint8_t PROD = 2 * 3 * 5;
constexpr std::uint8_t RM[K] = { 1, 7, 11, 13, 17, 19, 23, 29 };
constexpr std::uint8_t DR[K] = { 6, 4, 2, 4, 2, 4, 6, 2 };
constexpr std::uint8_t DF[K][K] = {
{ 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 0, 1, 1, 1, 1 },
{ 2, 2, 0, 2, 0, 2, 2, 1 }, { 3, 1, 1, 2, 1, 1, 3, 1 },
{ 3, 3, 1, 2, 1, 3, 3, 1 }, { 4, 2, 2, 2, 2, 2, 4, 1 },
{ 5, 3, 1, 4, 1, 3, 5, 1 }, { 6, 4, 2, 4, 2, 4, 6, 1 },
};
constexpr std::uint8_t DRP[K] = { 48, 32, 16, 32, 16, 32, 48, 16 };
constexpr std::uint8_t DFP[K][K] = {
{ 0, 0, 0, 0, 0, 0, 0, 8 }, { 8, 8, 8, 0, 8, 8, 8, 8 },
{ 16, 16, 0, 16, 0, 16, 16, 8 }, { 24, 8, 8, 16, 8, 8, 24, 8 },
{ 24, 24, 8, 16, 8, 24, 24, 8 }, { 32, 16, 16, 16, 16, 16, 32, 8 },
{ 40, 24, 8, 32, 8, 24, 40, 8 }, { 48, 32, 16, 32, 16, 32, 48, 8 },
};
constexpr std::uint8_t MASK[K][K] = {
{ 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 }, { 0x02, 0x20, 0x10, 0x01, 0x80, 0x08, 0x04, 0x40 },
{ 0x04, 0x10, 0x01, 0x40, 0x02, 0x80, 0x08, 0x20 }, { 0x08, 0x01, 0x40, 0x20, 0x04, 0x02, 0x80, 0x10 },
{ 0x10, 0x80, 0x02, 0x04, 0x20, 0x40, 0x01, 0x08 }, { 0x20, 0x08, 0x80, 0x02, 0x40, 0x01, 0x10, 0x04 },
{ 0x40, 0x04, 0x08, 0x80, 0x01, 0x10, 0x20, 0x02 }, { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 },
};
constexpr std::uint8_t OFFSET[K][K] = {
{ 0, 1, 2, 3, 4, 5, 6, 7, },
{ 1, 5, 4, 0, 7, 3, 2, 6, },
{ 2, 4, 0, 6, 1, 7, 3, 5, },
{ 3, 0, 6, 5, 2, 1, 7, 4, },
{ 4, 7, 1, 2, 5, 6, 0, 3, },
{ 5, 3, 7, 1, 6, 0, 4, 2, },
{ 6, 2, 3, 7, 0, 4, 5, 1, },
{ 7, 6, 5, 4, 3, 2, 1, 0, },
};
constexpr std::uint8_t mask_to_index(const std::uint8_t bits) {
switch (bits) {
case 1 << 0: return 0;
case 1 << 1: return 1;
case 1 << 2: return 2;
case 1 << 3: return 3;
case 1 << 4: return 4;
case 1 << 5: return 5;
case 1 << 6: return 6;
case 1 << 7: return 7;
default: assert(false);
}
}
} // namespace suisen::internal::sieve
#line 9 "library/number/sieve_of_eratosthenes.hpp"
namespace suisen {
template <unsigned int N>
class SimpleSieve {
private:
static constexpr unsigned int siz = N / internal::sieve::PROD + 1;
static std::uint8_t flag[siz];
public:
SimpleSieve() {
using namespace internal::sieve;
flag[0] |= 1;
unsigned int k_max = (unsigned int) std::sqrt(N + 2) / PROD;
for (unsigned int kp = 0; kp <= k_max; ++kp) {
for (std::uint8_t bits = ~flag[kp]; bits; bits &= bits - 1) {
const std::uint8_t mp = mask_to_index(bits & -bits), m = RM[mp];
unsigned int kr = kp * (PROD * kp + 2 * m) + m * m / PROD;
for (std::uint8_t mq = mp; kr < siz; kr += kp * DR[mq] + DF[mp][mq], ++mq &= 7) {
flag[kr] |= MASK[mp][mq];
}
}
}
}
std::vector<int> prime_list(unsigned int max_val = N) const {
using namespace internal::sieve;
std::vector<int> res { 2, 3, 5 };
res.reserve(max_val / 25);
for (unsigned int i = 0, offset = 0; i < siz and offset < max_val; ++i, offset += PROD) {
for (uint8_t f = ~flag[i]; f;) {
uint8_t g = f & -f;
res.push_back(offset + RM[mask_to_index(g)]);
f ^= g;
}
}
while (res.size() and (unsigned int) res.back() > max_val) res.pop_back();
return res;
}
bool is_prime(const unsigned int p) const {
using namespace internal::sieve;
switch (p) {
case 2: case 3: case 5: return true;
default:
switch (p % PROD) {
case RM[0]: return ((flag[p / PROD] >> 0) & 1) == 0;
case RM[1]: return ((flag[p / PROD] >> 1) & 1) == 0;
case RM[2]: return ((flag[p / PROD] >> 2) & 1) == 0;
case RM[3]: return ((flag[p / PROD] >> 3) & 1) == 0;
case RM[4]: return ((flag[p / PROD] >> 4) & 1) == 0;
case RM[5]: return ((flag[p / PROD] >> 5) & 1) == 0;
case RM[6]: return ((flag[p / PROD] >> 6) & 1) == 0;
case RM[7]: return ((flag[p / PROD] >> 7) & 1) == 0;
default: return false;
}
}
}
};
template <unsigned int N>
std::uint8_t SimpleSieve<N>::flag[SimpleSieve<N>::siz];
template <unsigned int N>
class Sieve {
private:
static constexpr unsigned int base_max = (N + 1) * internal::sieve::K / internal::sieve::PROD;
static unsigned int pf[base_max + internal::sieve::K];
public:
Sieve() {
using namespace internal::sieve;
pf[0] = 1;
unsigned int k_max = ((unsigned int) std::sqrt(N + 1) - 1) / PROD;
for (unsigned int kp = 0; kp <= k_max; ++kp) {
const int base_i = kp * K, base_act_i = kp * PROD;
for (int mp = 0; mp < K; ++mp) {
const int m = RM[mp], i = base_i + mp;
if (pf[i] == 0) {
unsigned int act_i = base_act_i + m;
unsigned int base_k = (kp * (PROD * kp + 2 * m) + m * m / PROD) * K;
for (std::uint8_t mq = mp; base_k <= base_max; base_k += kp * DRP[mq] + DFP[mp][mq], ++mq &= 7) {
pf[base_k + OFFSET[mp][mq]] = act_i;
}
}
}
}
}
bool is_prime(const unsigned int p) const {
using namespace internal::sieve;
switch (p) {
case 2: case 3: case 5: return true;
default:
switch (p % PROD) {
case RM[0]: return pf[p / PROD * K + 0] == 0;
case RM[1]: return pf[p / PROD * K + 1] == 0;
case RM[2]: return pf[p / PROD * K + 2] == 0;
case RM[3]: return pf[p / PROD * K + 3] == 0;
case RM[4]: return pf[p / PROD * K + 4] == 0;
case RM[5]: return pf[p / PROD * K + 5] == 0;
case RM[6]: return pf[p / PROD * K + 6] == 0;
case RM[7]: return pf[p / PROD * K + 7] == 0;
default: return false;
}
}
}
int prime_factor(const unsigned int p) const {
using namespace internal::sieve;
switch (p % PROD) {
case 0: case 2: case 4: case 6: case 8:
case 10: case 12: case 14: case 16: case 18:
case 20: case 22: case 24: case 26: case 28: return 2;
case 3: case 9: case 15: case 21: case 27: return 3;
case 5: case 25: return 5;
case RM[0]: return pf[p / PROD * K + 0] ? pf[p / PROD * K + 0] : p;
case RM[1]: return pf[p / PROD * K + 1] ? pf[p / PROD * K + 1] : p;
case RM[2]: return pf[p / PROD * K + 2] ? pf[p / PROD * K + 2] : p;
case RM[3]: return pf[p / PROD * K + 3] ? pf[p / PROD * K + 3] : p;
case RM[4]: return pf[p / PROD * K + 4] ? pf[p / PROD * K + 4] : p;
case RM[5]: return pf[p / PROD * K + 5] ? pf[p / PROD * K + 5] : p;
case RM[6]: return pf[p / PROD * K + 6] ? pf[p / PROD * K + 6] : p;
case RM[7]: return pf[p / PROD * K + 7] ? pf[p / PROD * K + 7] : p;
default: assert(false);
}
}
/**
* Returns a vector of `{ prime, index }`.
*/
std::vector<std::pair<int, int>> factorize(unsigned int n) const {
assert(0 < n and n <= N);
std::vector<std::pair<int, int>> prime_powers;
while (n > 1) {
int p = prime_factor(n), c = 0;
do { n /= p, ++c; } while (n % p == 0);
prime_powers.emplace_back(p, c);
}
return prime_powers;
}
/**
* Returns the divisors of `n`.
* It is NOT guaranteed that the returned vector is sorted.
*/
std::vector<int> divisors(unsigned int n) const {
assert(0 < n and n <= N);
std::vector<int> divs { 1 };
for (auto [prime, index] : factorize(n)) {
int sz = divs.size();
for (int i = 0; i < sz; ++i) {
int d = divs[i];
for (int j = 0; j < index; ++j) {
divs.push_back(d *= prime);
}
}
}
return divs;
}
};
template <unsigned int N>
unsigned int Sieve<N>::pf[Sieve<N>::base_max + internal::sieve::K];
} // namespace suisen
#line 1 "library/number/modint_2^61m1.hpp"
#line 6 "library/number/modint_2^61m1.hpp"
namespace suisen {
// reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
struct modint2p61m1 {
using self = modint2p61m1;
constexpr modint2p61m1(): v(0) {}
constexpr modint2p61m1(uint64_t v): v(fast_mod(v)) {}
static constexpr uint64_t mod() {
return _mod;
}
static constexpr uint64_t fast_mod(uint64_t v) {
constexpr uint32_t mid = 61;
constexpr uint64_t mask = (uint64_t(1) << mid) - 1;
uint64_t u = v >> mid;
uint64_t d = v & mask;
uint64_t res = u + d;
if (res >= _mod) res -= _mod;
return res;
}
constexpr uint64_t val() const {
return v;
}
constexpr self& operator+=(const self& rhs) {
v += rhs.v;
if (v >= _mod) v -= _mod;
return *this;
}
constexpr self& operator-=(const self& rhs) {
if (v < rhs.v) v += _mod;
v -= rhs.v;
return *this;
}
constexpr self& operator*=(const self& rhs) {
uint64_t au = v >> mid31; // < 2^30
uint64_t ad = v & mask31; // < 2^31
uint64_t bu = rhs.v >> mid31; // < 2^30
uint64_t bd = rhs.v & mask31; // < 2^31
// a * b
// = (au * 2^31 + ad) * (bu * 2^31 + bd)
// = au * bu * 2^62 # au * bu * 2^62 ≡ au * bu * 2 < 2^61
// + (au * bd + ad * bu) * 2^31 # m := au * bd + ad * bu
// # m <= 2 * (2^31 - 1) * (2^30 - 1) = 2^62 - 6 * 2^30 + 2
// # m = mu * 2^30 + md (0 <= mu < 2^32, 0 <= md < 2^30)
// # m * 2^31 ≡ mu + md * 2^31 < 2^61 + 2^31
// + ad * bd # ad * bd <= (2^31 - 1) ** 2 = 2^62 - 2^32 + 1 < 2^62 - 2^31
// ≡ au * bu * 2 + mu + md * 2^31 + ad * bd < 2^63
uint64_t m = au * bd + ad * bu;
uint64_t mu = m >> mid30;
uint64_t md = m & mask30;
v = fast_mod((au * bu << 1) + mu + (md << 31) + ad * bd);
return *this;
}
constexpr friend self operator+(const self& l, const self& r) { return self(l) += r; }
constexpr friend self operator-(const self& l, const self& r) { return self(l) -= r; }
constexpr friend self operator*(const self& l, const self& r) { return self(l) *= r; }
constexpr friend bool operator==(const self& l, const self& r) { return l.v == r.v; }
constexpr self pow(long long b) const {
assert(b >= 0);
self x = 1, p = *this;
for (; b; b >>= 1) {
if (b & 1) x *= p;
p *= p;
}
return x;
}
constexpr self inv() const {
// a ** (p - 2) = a ** (2**61 - 3)
// 2**61 - 3 = 0001_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1111_1101
self x = *this, p = *this * *this;
for (int i = 2; i <= 60; ++i) {
x *= (p *= p);
}
return x;
}
private:
static constexpr uint64_t _mod = (uint64_t(1) << 61) - 1; // 2**61-1 : prime
static constexpr uint32_t mid31 = 31;
static constexpr uint64_t mask31 = (uint64_t(1) << 31) - 1;
static constexpr uint32_t mid30 = 30;
static constexpr uint64_t mask30 = (uint64_t(1) << mid30) - 1;
uint64_t v;
};
} // namespace suisen
#line 1 "library/datastructure/bbst/red_black_segment_tree.hpp"
#line 1 "library/datastructure/bbst/red_black_tree_base.hpp"
#line 5 "library/datastructure/bbst/red_black_tree_base.hpp"
#include <sstream>
#include <string>
#include <tuple>
#line 1 "library/util/object_pool.hpp"
#include <deque>
#line 6 "library/util/object_pool.hpp"
namespace suisen {
template <typename T, bool auto_extend = false>
struct ObjectPool {
using value_type = T;
using value_pointer_type = T*;
template <typename U>
using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>;
container_type<value_type> pool;
container_type<value_pointer_type> stock;
decltype(stock.begin()) it;
ObjectPool() : ObjectPool(0) {}
ObjectPool(int siz) : pool(siz), stock(siz) {
clear();
}
int capacity() const { return pool.size(); }
int size() const { return it - stock.begin(); }
value_pointer_type alloc() {
if constexpr (auto_extend) ensure();
return *it++;
}
void free(value_pointer_type t) {
*--it = t;
}
void clear() {
int siz = pool.size();
it = stock.begin();
for (int i = 0; i < siz; i++) stock[i] = &pool[i];
}
void ensure() {
if (it != stock.end()) return;
int siz = stock.size();
for (int i = siz; i <= siz * 2; ++i) {
stock.push_back(&pool.emplace_back());
}
it = stock.begin() + siz;
}
};
} // namespace suisen
#line 9 "library/datastructure/bbst/red_black_tree_base.hpp"
namespace suisen::bbst::internal {
template <typename T, typename Derived>
struct RedBlackTreeNodeBase {
enum RedBlackTreeNodeColor { RED, BLACK };
using base_type = void;
using size_type = int;
using value_type = T;
using node_type = Derived;
using tree_type = node_type*;
using color_type = RedBlackTreeNodeColor;
RedBlackTreeNodeBase() = default;
static inline ObjectPool<node_type> pool{};
static void init_pool(int siz) { pool = ObjectPool<node_type>(siz); }
static int node_num() { return pool.size(); }
static tree_type empty_tree() { return nullptr; }
static size_type size(tree_type node) { return node ? node->_siz : 0; }
static bool empty(tree_type node) { return not node; }
template <bool force_black_root = true>
static tree_type merge(tree_type l, tree_type r) {
if (not l) return r;
if (not r) return l;
tree_type res = nullptr;
if (size_type hl = height(l), hr = height(r); hl > hr) {
l = node_type::push(l);
tree_type c = l->_ch[1] = merge<false>(l->_ch[1], r);
if (l->_col == BLACK and c->_col == RED and color(c->_ch[1]) == RED) {
std::swap(l->_col, c->_col);
if (std::exchange(l->_ch[0]->_col, BLACK) == BLACK) return rotate(l, 1);
}
res = node_type::update(l);
} else if (hr > hl) {
r = node_type::push(r);
tree_type c = r->_ch[0] = merge<false>(l, r->_ch[0]);
if (r->_col == BLACK and c->_col == RED and color(c->_ch[0]) == RED) {
std::swap(r->_col, c->_col);
if (std::exchange(r->_ch[1]->_col, BLACK) == BLACK) return rotate(r, 0);
}
res = node_type::update(r);
} else {
res = create_branch(l, r);
}
if constexpr (force_black_root) res->_col = BLACK;
return res;
}
static std::pair<tree_type, tree_type> split(tree_type node, size_type k) {
if (not node) return { nullptr, nullptr };
node = node_type::push(node);
if (k == 0) return { nullptr, node };
if (k == size(node)) return { node, nullptr };
tree_type l = std::exchange(node->_ch[0], nullptr);
tree_type r = std::exchange(node->_ch[1], nullptr);
free_node(node);
if (color(l) == RED) l->_col = BLACK;
if (color(r) == RED) r->_col = BLACK;
size_type szl = size(l);
tree_type m;
if (k < szl) {
std::tie(l, m) = split(l, k);
return { l, merge(m, r) };
}
if (k > szl) {
std::tie(m, r) = split(r, k - szl);
return { merge(l, m), r };
}
return { l, r };
}
static std::tuple<tree_type, tree_type, tree_type> split_range(tree_type node, size_type l, size_type r) {
auto [tlm, tr] = split(node, r);
auto [tl, tm] = split(tlm, l);
return { tl, tm, tr };
}
static tree_type insert(tree_type node, size_type k, const value_type& val) {
auto [tl, tr] = split(node, k);
return merge(merge(tl, create_leaf(val)), tr);
}
static tree_type push_front(tree_type node, const value_type &val) { return insert(node, 0, val); }
static tree_type push_back(tree_type node, const value_type &val) { return insert(node, size(node), val); }
static std::pair<tree_type, value_type> erase(tree_type node, size_type k) {
auto [tl, tm, tr] = split_range(node, k, k + 1);
value_type erased_value = tm->_val;
free_node(tm);
return { merge(tl, tr) , erased_value };
}
static std::pair<tree_type, value_type> pop_front(tree_type node) { return erase(node, 0); }
static std::pair<tree_type, value_type> pop_back(tree_type node) { return erase(node, size(node) - 1); }
template <typename Fun>
static tree_type update_value(tree_type node, size_type k, Fun &&fun) {
auto [tl, top, tr] = split_range(node, k, k + 1);
top->_val = fun(top->_val);
return merge(merge(tl, top), tr);
}
static tree_type set(tree_type node, size_type k, value_type val) {
return update_value(node, k, [&val]{ return val; });
}
static std::pair<tree_type, value_type> get(tree_type node, size_type k) {
auto [tl, top, tr] = split_range(node, k, k + 1);
value_type res = top->_val;
return { merge(merge(tl, top), tr), res };
}
template <typename Seq>
static tree_type build(const Seq& a, int l, int r) {
if (r - l == 1) return create_leaf(a[l]);
int m = (l + r) >> 1;
return merge(build(a, l, m), build(a, m, r));
}
template <typename Seq>
static tree_type build(const Seq& a) {
return a.empty() ? empty_tree() : build(a, 0, a.size());
}
template <typename OutputIterator>
static void dump(tree_type node, OutputIterator it) {
if (empty(node)) return;
auto dfs = [&](auto dfs, tree_type cur) -> void {
if (cur->is_leaf()) {
*it++ = cur->_val;
return;
}
dfs(dfs, cur->_ch[0]);
dfs(dfs, cur->_ch[1]);
};
dfs(dfs, node);
}
// Don't use on persistent tree.
static void free(tree_type node) {
auto dfs = [&](auto dfs, tree_type cur) -> void {
if (not cur) return;
dfs(dfs, cur->_ch[0]);
dfs(dfs, cur->_ch[1]);
free_node(cur);
};
dfs(dfs, node);
}
template <typename ToStr>
static std::string to_string(tree_type node, ToStr f) {
std::vector<value_type> dat;
node_type::dump(node, std::back_inserter(dat));
std::ostringstream res;
int siz = dat.size();
res << '[';
for (int i = 0; i < siz; ++i) {
res << f(dat[i]);
if (i != siz - 1) res << ", ";
}
res << ']';
return res.str();
}
static std::string to_string(tree_type node) {
return to_string(node, [](const auto &e) { return e; });
}
static void check_rbtree_properties(tree_type node) {
assert(color(node) == BLACK);
auto dfs = [&](auto dfs, tree_type cur) -> int {
if (not cur) return 0;
if (cur->_col == RED) {
assert(color(cur->_ch[0]) == BLACK);
assert(color(cur->_ch[1]) == BLACK);
}
int bl = dfs(dfs, cur->_ch[0]);
int br = dfs(dfs, cur->_ch[1]);
assert(bl == br);
return bl + (cur->_col == BLACK);
};
dfs(dfs, node);
}
protected:
color_type _col;
tree_type _ch[2]{ nullptr, nullptr };
value_type _val;
size_type _siz, _lev;
RedBlackTreeNodeBase(const value_type& val) : _col(BLACK), _val(val), _siz(1), _lev(0) {}
RedBlackTreeNodeBase(tree_type l, tree_type r) : _col(RED), _ch{ l, r }, _siz(l->_siz + r->_siz), _lev(l->_lev + (l->_col == BLACK)) {}
static void clear_pool() { pool.clear(); }
static int pool_capacity() { return pool.capacity(); }
static color_type color(tree_type node) { return node ? node->_col : BLACK; }
static size_type height(tree_type node) { return node ? node->_lev : 0; }
bool is_leaf() const { return not (_ch[0] or _ch[1]); }
static tree_type clone(tree_type node) {
return node;
}
static tree_type update(tree_type node) {
node->_siz = node->is_leaf() ? 1 : size(node->_ch[0]) + size(node->_ch[1]);
node->_lev = node->_ch[0] ? height(node->_ch[0]) + (node->_ch[0]->_col == BLACK) : 0;
return node;
}
static tree_type push(tree_type node) {
return node;
}
static tree_type rotate(tree_type node, int index) {
node = node_type::push(node);
tree_type ch_node = node_type::push(node->_ch[index]);
node->_ch[index] = std::exchange(ch_node->_ch[index ^ 1], node);
return node_type::update(node), node_type::update(ch_node);
}
static tree_type create_leaf(const value_type& val = value_type{}) {
return &(*pool.alloc() = node_type(val));
}
static tree_type create_branch(tree_type l, tree_type r) {
return node_type::update(&(*pool.alloc() = node_type(l, r)));
}
static void free_node(tree_type node) {
if (node) pool.free(node);
}
};
} // namespace suisen
#line 5 "library/datastructure/bbst/red_black_segment_tree.hpp"
namespace suisen::bbst::segtree {
template <typename T, T(*op)(T, T), T(*e)(), template <typename, typename> typename BaseNode = internal::RedBlackTreeNodeBase>
struct RedBlackTreeNode : public BaseNode<T, RedBlackTreeNode<T, op, e, BaseNode>> {
using base_type = BaseNode<T, RedBlackTreeNode<T, op, e, BaseNode>>;
using node_type = typename base_type::node_type;
using tree_type = typename base_type::tree_type;
using size_type = typename base_type::size_type;
using value_type = typename base_type::value_type;
friend base_type;
friend typename base_type::base_type;
RedBlackTreeNode() : base_type() {}
static std::pair<tree_type, value_type> prod(tree_type node, size_type l, size_type r) {
auto [tl, tm, tr] = base_type::split_range(node, l, r);
value_type res = value(tm);
return { base_type::merge(base_type::merge(tl, tm), tr), res };
}
static value_type prod_all(tree_type node) {
return value(node);
}
private:
RedBlackTreeNode(const value_type& val) : base_type(val) {}
RedBlackTreeNode(tree_type l, tree_type r) : base_type(l, r) {}
static value_type value(tree_type node) { return node ? node->_val : e(); }
static tree_type update(tree_type node) {
base_type::update(node);
node->_val = op(value(node->_ch[0]), value(node->_ch[1]));
return node;
}
};
}
#line 9 "library/string/dynamic_rolling_hash.hpp"
namespace suisen {
namespace internal::dynamic_rolling_hash {
struct BaseGen {
static inline std::mt19937_64 rng{ std::random_device{}() };
static inline std::uniform_int_distribution<uint64_t> dist{ 0, modint2p61m1::mod() - 1 };
static uint32_t generate() {
return dist(rng);
}
};
template <size_t id>
uint32_t base() {
static uint32_t _base = 0;
return _base ? _base : (_base = BaseGen::generate());
}
template <size_t base_num_>
struct Hash {
static constexpr size_t base_num = base_num_;
using child_type = Hash<base_num - 1>;
using hash_type = std::array<uint64_t, base_num>;
modint2p61m1 hash;
modint2p61m1 offset;
child_type hash_lo;
Hash() : Hash(0) {}
template <typename T>
Hash(const T& val): hash(val), offset(base<base_num>()), hash_lo(val) {}
operator hash_type() const {
hash_type res;
store_hash(res);
return res;
}
template <typename Container>
void store_hash(Container& h) const {
h[base_num - 1] = hash.val();
hash_lo.store_hash(h);
}
static Hash identity() {
return { 0, 1, child_type::identity() };
}
static Hash merge(const Hash &l, const Hash &r) {
return { l.hash * r.offset + r.hash, l.offset * r.offset, child_type::merge(l.hash_lo, r.hash_lo) };
}
static Hash merge_noref(Hash l, Hash r) {
return merge(l, r);
}
private:
Hash(const modint2p61m1& hash, const modint2p61m1& offset, const child_type& hash_lo): hash(hash), offset(offset), hash_lo(hash_lo) {}
};
template <>
struct Hash<1> {
static constexpr size_t base_num = 1;
modint2p61m1 hash;
modint2p61m1 offset;
using hash_type = uint64_t;
Hash() : Hash(0) {}
template <typename T>
Hash(const T& val): hash(val), offset(base<base_num>()) {}
operator hash_type() const {
return hash.val();
}
template <typename Container>
void store_hash(Container& h) const {
h[0] = hash.val();
}
static Hash identity() {
return { 0, 1 };
}
static Hash merge(const Hash &l, const Hash &r) {
return { l.hash * r.offset + r.hash, l.offset * r.offset };
}
static Hash merge_noref(Hash l, Hash r) {
return merge(l, r);
}
private:
Hash(const modint2p61m1& hash, const modint2p61m1& offset): hash(hash), offset(offset) {}
};
}
template <std::size_t base_num>
using Hash = internal::dynamic_rolling_hash::Hash<base_num>;
template <size_t base_num_ = 1>
struct DynamicRollingHash {
static constexpr size_t base_num = base_num_;
private:
using hash_ = Hash<base_num>;
using node = bbst::segtree::RedBlackTreeNode<hash_, hash_::merge_noref, hash_::identity>;
node* _seq;
public:
using hash = typename hash_::hash_type;
DynamicRollingHash(): _seq(nullptr) {}
template <typename Seq>
DynamicRollingHash(const Seq& a): _seq(node::build(a)) {}
static void init_pool(size_t reserving_node_num) {
node::init_pool(reserving_node_num);
}
template <typename T>
void set(size_t k, const T& val) {
_seq = node::update_value(_seq, k, val);
}
template <typename T>
void insert(size_t k, const T& val) {
_seq = node::insert(_seq, k, val);
}
template <typename T>
void push_back(const T& val) {
insert(node::size(_seq), val);
}
template <typename T>
void push_front(const T& val) {
insert(0, val);
}
void erase(size_t k) {
_seq = node::erase(_seq, k).first;
}
void pop_back() {
erase(node::size(_seq) - 1);
}
void pop_front() {
erase(0);
}
hash operator()(int l, int r) {
hash_ res;
std::tie(_seq, res) = node::prod(_seq, l, r);
return res;
}
};
}