matsutaku-library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/yosupo/static_rmq-constant_rmq.test.cpp
- View this file on GitHub
- Last update: 2024-07-11 22:21:57+09:00
- Problem: https://judge.yosupo.jp/problem/staticrmq
Code
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "include/mtl/range_minimum_query.hpp"
#include <iostream>
using namespace std;
int main() {
int n,q; cin>>n>>q;
vector<int> A(n);
for (int i = 0; i < n; i++) cin>>A[i];
Rmq<int> st(A.begin(), A.end());
while (q--) {
int l,r; cin>>l>>r;
auto min_idx = st.rmq(l,r);
// if (!(l <= min_idx and min_idx < r)) {
// std::cerr<<"l r min_idx "<<l<<' '<<r<<' '<<min_idx<<std::endl;
// }
// assert(l <= min_idx and min_idx < r);
cout<<A[min_idx]<<endl;
}
}#line 1 "test/yosupo/static_rmq-constant_rmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#include <cassert>
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif
namespace bm {
/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
return std::popcount(x);
#else
return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_zero(x);
#else
return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_one(x);
#else
return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
constexpr uint64_t hmask = 0x8080808080808080ull;
constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
auto a = x & hmask;
auto b = x & lmask;
b = hmask - b;
b = ~b;
auto c = (a | b) & hmask;
c *= 0x0002040810204081ull;
return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
if (x & 0x80)
return 8;
uint64_t p = uint64_t(x) * 0x0101010101010101ull;
p -= 0x8040201008040201ull;
p = ~p & 0x8080808080808080ull;
p = (p >> 7) * 0x0101010101010101ull;
p >>= 56;
return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
assert(x != 0);
return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
assert(x != 0);
return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_zero(x);
#else
if (x == 0)
return 64;
auto i = mssb8(summary(x));
auto j = mssb8(bextr(x, 8 * i, 8));
return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_one(x);
#else
return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
return clo(x);
}
inline constexpr unsigned clz8(uint8_t x) {
return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
return x;
}
/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::has_single_bit(x);
#else
return x != 0 && (x & (x - 1)) == 0;
#endif
}
/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::bit_width(x);
#else
return 64 - clz(x);
#endif
}
/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_ceil(x);
#else
if (x == 0) return 1;
return 1ull << bit_width(x - 1);
#endif
}
/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_floor(x);
#else
if (x == 0) return 0;
return 1ull << (bit_width(x) - 1);
#endif
}
} // namespace bm
#line 3 "include/mtl/succinct/select.hpp"
#include <array>
struct select64 {
using size_type = uint8_t;
static struct make_select_table {
using bitmap_type = uint8_t;
std::array<std::array<size_type, 9>, 1<<8> tb;
make_select_table() {
for (int i = 0; i < 1<<8; i++) {
int c = 0;
int x = i;
tb[i].fill(8);
for (int j = 0; j < 8; j++) {
if (x & 1)
tb[i][++c] = j;
x >>= 1;
}
}
}
size_type operator()(bitmap_type bitmap, size_type ith) const {
return tb[bitmap][ith];
}
} sel_tb;
template<bool B>
static constexpr size_type select(size_type ith, uint64_t bitmap) { // 0-indexed
assert(ith < 64);
ith++; // to 1-index
// Find byte
uint64_t w = bitmap;
if constexpr (!B) w = ~w;
auto _bs = (uint64_t) bm::popcnt_e8(w) * 0x0101010101010100ull;
auto bs = (const uint8_t*) &_bs;
size_type b = 0;
auto o = ith;
/* Following bit-manipulates code is same as ... */
// {
// auto d = 8;
// while (d > 1) {
// auto c = b + d/2;
// if (bs[c] < o)
// b = c;
// d /= 2;
// }
// }
{
uint64_t x = (uint64_t) o * 0x0101010101010101ull;
uint64_t bmx = (_bs | 0x8080808080808080ull) - x;
uint64_t y = ((bmx & 0x8080808080808080ull) * 0x02040810204081ull) >> (64-8);
size_type nb = bm::ctz8(y) - 1;
// assert(b == nb);
b = nb;
}
// Calc select
auto r = o - bs[b];
uint8_t byte = ((const uint8_t*)(&w))[b];
assert(r and r <= (size_type)bm::popcnt(byte));
return b * 8 + sel_tb(byte, r);
}
static constexpr size_type select1(size_type ith, uint64_t bitmap) {
return select<1>(ith, bitmap);
}
static constexpr size_type select0(size_type ith, uint64_t bitmap) {
return select<0>(ith, bitmap);
}
};
typename select64::make_select_table select64::sel_tb;
#line 3 "include/mtl/succinct/bv.hpp"
#include <vector>
#include <cstddef>
#line 6 "include/mtl/succinct/bv.hpp"
#include <bitset>
#include <iostream>
#if __cpp_concepts >= 202002L
#include <concepts>
template<class T>
concept ConstructableBV = requires(T t, size_t s) {
{ t.size() } -> std::same_as<size_t>;
{ t.word_size() } -> std::same_as<size_t>;
{ t.get_word(s) } -> std::convertible_to<uint64_t>;
};
#endif
template<
#if __cpp_concepts >= 202002L
ConstructableBV
#else
class
#endif
BitVec, unsigned WordSize>
struct BV {
static_assert(WordSize <= 64, "WordSize must be <= 64");
static constexpr unsigned S = WordSize;
static constexpr unsigned S_PER_L = 8;
static constexpr unsigned L = S*S_PER_L;
using bitvec_type = BitVec;
const bitvec_type* bm_;
std::vector<uint64_t> _r, _s, _zs;
BV() = default;
explicit BV(const bitvec_type* bm) {
build(bm);
}
void set_ptr(const bitvec_type* bm) {
bm_ = bm;
}
void build(const bitvec_type* bm) {
set_ptr(bm);
const auto num_l = (bm->size() + L-1) / L;
_r.assign((num_l + 1) * 2, 0);
_s.clear();
_s.push_back(0);
_zs.clear();
_zs.push_back(0);
uint64_t sum = 0;
for (size_t l = 0; l < num_l; ++l) {
auto psum = sum;
uint64_t sum_l = 0;
for (size_t s = 0; s < S_PER_L; ++s) {
if (l * S_PER_L + s < bm->word_size())
sum_l += bm::popcnt(bm->get_word(l * S_PER_L + s));
if (s < S_PER_L-1)
_r[l * 2 + 1] |= sum_l << ((7-(s+1)) * 9);
}
sum += sum_l;
_r[(l + 1) * 2] = sum;
if (psum / L != sum / L) {
_s.push_back(l);
}
if ((L*l - psum) / L != (L*(l+1) - sum) / L) {
_zs.push_back(l);
}
}
_s.push_back(num_l);
_zs.push_back(num_l);
}
template<bool B>
size_t get_l(size_t l) const {
auto b = _r[l*2];
return B ? b : l * L - b;
}
static constexpr size_t s_off(size_t s) {
return (7-s) * 9;
}
template<bool B>
size_t get_s(size_t l, size_t s) const {
auto b = (_r[l*2+1] >> s_off(s)) % (1ull<<9);
return B ? b : s * S - b;
}
uint64_t mask(size_t width) const {
return width == 64 ? ~0ull : (1ull << width) - 1;
}
size_t rank1(size_t i) const {
auto l = i / L;
auto s = i % L / S;
auto q = i / S;
auto r = i % S;
assert(bm_ != nullptr);
auto w = bm_->get_word(q) & mask(r);
return get_l<1>(l) +
get_s<1>(l, s) +
bm::popcnt(w);
}
size_t rank0(size_t i) const {
return i - rank1(i);
}
template<bool B>
size_t rank(size_t i) const {
if constexpr (B)
return rank1(i);
else
return rank0(i);
}
static struct l_block_cap_mask {
uint64_t mask;
constexpr l_block_cap_mask() : mask(0) {
for (unsigned i = 0; i < S_PER_L; i++) {
uint64_t cap = i * S;
mask |= cap << s_off(i);
}
}
} l_block_cap;
template<bool B>
size_t select(size_t ith) const {
auto n = ith+1; // to 1-indexed
if (n > rank<B>(bm_->size()))
return bm_->size();
// Find L block
auto& idx = B ? _s : _zs;
size_t l = idx[n / L];
{
auto r = idx[n / L + 1] + 1;
while (l+1 < r) {
auto c = l + (r-l)/2;
if (get_l<B>(c) < n)
l = c;
else
r = c;
}
}
// Find S block
size_t s = 0;
auto m = n - get_l<B>(l);
/* Following bit-manipulates code is same as ... */
// {
// auto d = 8;
// while (d > 1) {
// auto c = s + d/2;
// if (get_s<B>(l, c) < m)
// s = c;
// d /= 2;
// }
// }
{
uint64_t x = (uint64_t) (m-1) * 0x0040201008040201ull;
uint64_t a = _r[l*2+1];
if constexpr (!B)
a = l_block_cap.mask - a; // to 0s sum
uint64_t xda = x - a;
uint64_t sm = 0x4020100804020100ull;
uint64_t ok = (~x | a) & sm;
uint64_t ng = (~x & a) & sm;
uint64_t y = ((x ^ a ^ xda) & ok) | ng;
y = y * 0x0001010101010101ull >> (64-1-7);
auto id = bm::clz8(y)-1;
auto clo = bm::clz((~xda << 1 | 1) << (9*id));
auto ns = id + (clo ? (clo - 1) / 9 : 0);
s = ns;
}
// Calc select
auto o = m - get_s<B>(l, s);
uint64_t w = bm_->get_word(l * S_PER_L + s);
return l * L +
s * S +
select64::select<B>(o-1, w);
}
size_t select1(size_t ith) const {
return select<1>(ith);
}
size_t select0(size_t ith) const {
return select<0>(ith);
}
};
template<class BitVec, unsigned WordSize>
typename BV<BitVec, WordSize>::l_block_cap_mask BV<BitVec, WordSize>::l_block_cap;
#line 8 "include/mtl/succinct/bitmap.hpp"
#include <iterator>
auto t = std::iterator_traits<std::vector<bool>::iterator>::iterator_category();
/// Bitmap is likes std::vector<bool> with advanced operations
struct Bitmap {
using value_type = bool;
using W = uint64_t;
std::vector<W> arr;
size_t sz;
static constexpr size_t required_word_size(size_t n) {
return (n+63) / 64;
}
static constexpr W word_filled_by(bool bit) {
return bit ? 0xFFFFFFFFFFFFFFFF : 0;
}
explicit Bitmap(size_t n = 0, bool bit = false)
: arr(required_word_size(n), word_filled_by(bit)), sz(n) {}
template<typename It>
Bitmap(It begin, It end) : sz(0) {
using trait = std::iterator_traits<It>;
using iterator_category = typename trait::iterator_category;
static_assert(std::is_base_of<std::input_iterator_tag, iterator_category>::value, "");
static_assert(std::is_convertible<typename trait::value_type, bool>::value, "");
if constexpr (std::is_base_of<std::random_access_iterator_tag, iterator_category>::value) {
arr.reserve(required_word_size(std::distance(begin, end)));
}
for (auto it = begin; it != end; ++it)
push_back((bool)*it);
}
size_t size() const { return sz; }
bool empty() const { return size() == 0; }
void push_back(bool bit) {
auto r = sz % 64;
if (r == 0) {
arr.push_back((W)bit);
} else {
if (bit)
arr.back() |= 1ull << r;
else
arr.back() &= ~(1ull << r);
}
++sz;
}
void pop_back() {
--sz;
}
void resize(size_t new_size, bool bit=false) { // TODO: fix when bit = true
auto old_size = size();
sz = new_size;
if (new_size < old_size) {
return;
}
arr.resize(required_word_size(new_size), word_filled_by(bit));
auto r = old_size % 64;
if (r) {
W mask = (1ull << r) - 1;
if (bit)
arr[old_size / 64] |= ~mask;
else
arr[old_size / 64] &= mask;
}
}
void assign(size_t new_size, bool bit) {
sz = new_size;
arr.assign(required_word_size(new_size), word_filled_by(bit));
}
void reserve(size_t reserved_size) {
arr.reserve(required_word_size(reserved_size));
}
struct const_reference;
struct reference;
template<bool>
struct _iterator;
using const_iterator = _iterator<true>;
using iterator = _iterator<false>;
const_reference operator[](size_t i) const {
return const_reference(arr.data() + i / 64, 1ull << (i % 64));
}
reference operator[](size_t i) {
return {arr.data() + i / 64, 1ull << (i % 64)};
}
const_reference get(size_t i) const {
return operator[](i);
}
/**
* Usable without pre-set required size
*/
void set(size_t i, bool b) {
if (i >= size())
resize(i + 1);
operator[](i) = b;
}
/**
* No build process is needed
*/
void build() const {}
void move_or_build(Bitmap&& src) {
*this = std::move(src);
}
const_iterator begin() const { return const_iterator(arr.data(), 0); }
iterator begin() { return iterator(arr.data(), 0); }
const_iterator cbegin() const { return begin(); }
const_iterator end() const { return const_iterator(arr.data() + sz / 64, sz % 64); }
iterator end() { return iterator(arr.data() + sz / 64, sz % 64); }
const_iterator cend() const { return end(); }
template<bool Const>
struct reference_base {
using _pointer = typename std::conditional<Const, const W*, W*>::type;
using _iterator = typename std::conditional<Const, const_iterator, iterator>::type;
_pointer ptr;
W mask;
reference_base(_pointer ptr, W mask) : ptr(ptr), mask(mask) {}
reference_base(const reference_base&) = delete;
reference_base& operator=(const reference_base&) = delete;
reference_base(reference_base&&) noexcept = default;
reference_base& operator=(reference_base&&) noexcept = default;
inline operator bool() const {
return (*ptr & mask) != 0;
}
inline bool operator==(bool r) const {
return (bool) *this == r;
}
inline friend bool operator==(bool l, const reference_base& r) {
return r == l;
}
inline bool operator!=(bool r) const {
return (bool) *this != r;
}
inline friend bool operator!=(bool l, const reference_base& r) {
return r != l;
}
_iterator operator&() const {
return {ptr, bm::ctz(mask)};
}
std::ostream& operator<<(std::ostream& os) const {
return os << (bool) *this;
}
};
struct const_reference : public reference_base<true> {
using _base = reference_base<true>;
const_reference(_base::_pointer ptr, W mask) : _base(ptr, mask) {}
const_reference(const reference& rhs) : _base(rhs.ptr, rhs.mask) {}
};
struct reference : public reference_base<false> {
using _base = reference_base<false>;
reference(_base::_pointer ptr, W mask) : _base(ptr, mask) {}
inline reference& operator=(bool bit) {
if (bit)
*ptr |= mask;
else
*ptr &= ~mask;
return *this;
}
inline reference& operator|=(bool bit) {
if (bit)
*ptr |= mask;
return *this;
}
inline reference& operator&=(bool bit) {
if (!bit)
*ptr &= ~mask;
return *this;
}
template<bool C>
inline reference& operator=(const reference_base<C>& rhs) {
return *this = (bool) rhs;
}
reference(const reference& rhs) = delete;
reference(reference&& rhs) noexcept = default;
reference& operator=(reference&& rhs) noexcept = default;
std::istream& operator>>(std::istream& is) {
bool b;
is >> b;
operator=(b);
return is;
}
};
template<bool Const>
struct _iterator {
using iterator_category = std::random_access_iterator_tag;
using value_type = bool;
using difference_type = std::ptrdiff_t;
using pointer = iterator;
using reference = typename std::conditional<Const, const_reference, Bitmap::reference>::type;
using _pointer = typename std::conditional<Const, const W*, W*>::type;
_pointer ptr;
unsigned ctz;
_iterator(_pointer ptr, unsigned ctz) : ptr(ptr), ctz(ctz) {}
inline reference operator*() const {
return reference(ptr, 1ull << ctz);
}
template<bool C>
inline bool operator==(const _iterator<C>& r) const {
return ptr == r.ptr and ctz == r.ctz;
}
template<bool C>
inline bool operator!=(const _iterator<C>& r) const {
return ptr != r.ptr or ctz != r.ctz;
}
inline _iterator& operator++() {
if (ctz % 64 < 63) {
++ctz;
} else {
++ptr;
ctz = 0;
}
return *this;
}
inline _iterator operator++(int) {
_iterator ret = *this;
operator++();
return ret;
}
inline _iterator& operator--() {
if (ctz % 64 > 0) {
--ctz;
} else {
--ptr;
ctz = 63;
}
return *this;
}
inline _iterator operator--(int) {
_iterator ret = *this;
operator--();
return ret;
}
inline _iterator& operator+=(std::ptrdiff_t d) {
if (d < 0)
return operator-=(-d);
auto r = d % 64;
if (ctz + r < 64) {
ptr += d / 64;
ctz += r;
} else {
ptr += d / 64 + 1;
ctz = (ctz + r) - 64;
}
return *this;
}
inline _iterator operator+(std::ptrdiff_t d) const {
return _iterator(*this) += d;
}
inline _iterator& operator-=(std::ptrdiff_t d) {
if (d < 0)
return operator+=(-d);
auto r = d % 64;
if (r <= ctz) {
ptr -= d / 64;
ctz -= r;
} else {
ptr -= d / 64 + 1;
ctz = (ctz + 64 - r) - 64;
}
return *this;
}
inline _iterator operator-(std::ptrdiff_t d) const {
return _iterator(*this) -= d;
}
inline reference operator[](size_t i) const {
return *(*this + i);
}
};
void range_set(size_t b, size_t e, uint64_t x) {
if (b >= e) return;
auto r = b % 64;
auto w = e-b;
auto mask = w < 64 ? (1ull << w) - 1 : ~0ull;
assert(x <= mask);
arr[b/64] = (arr[b/64] & ~(mask << r)) | x << r;
if (mask + r > 64) {
arr[b/64+1] = (arr[b/64+1] & ~(mask >> (64-r))) | x >> (64-r);
}
}
uint64_t range_get(size_t b, size_t e) const {
if (b >= e) return 0;
assert(e-b <= 64);
auto r = b % 64;
auto w = e-b;
auto mask = w < 64 ? (1ull << w) - 1 : ~0ull;
auto x = arr[b/64] >> r;
if (w + r > 64)
x |= arr[b/64+1] << (64-r);
return x & mask;
}
const uint64_t& get_word(size_t wi) const {
return arr[wi];
}
size_t word_size() const {
return arr.size();
}
// using rank_select_type = BV<Bitmap, 64>;
};
#line 4 "include/mtl/succinct/ty.hpp"
#include <limits>
#line 6 "include/mtl/succinct/ty.hpp"
#include <algorithm>
#line 8 "include/mtl/succinct/ty.hpp"
/**
* @brief TY: Store increasing sequence of integers.
* Memory needs for store nth integers O(n log d) bits
* which d is max diff of consecutive elements.
*/
template<class T, class DiffType = int16_t>
class TY {
using value_type = T;
static constexpr auto block_size = sizeof(value_type) * 8;
using diff_value_type = DiffType;
static constexpr unsigned max_diff = std::numeric_limits<diff_value_type>::max();
private:
std::vector<value_type> head;
std::vector<diff_value_type> diff;
public:
TY() = default;
template<class It>
TY(It first, It last) {
assert(std::is_sorted(first, last));
reserve(std::distance(first, last));
for (auto it = first; it != last; it++) {
push_back(*it);
}
}
size_t size() const {
return head.size() + diff.size();
}
bool empty() const { return size() == 0; }
void reserve(size_t n) {
head.reserve((n + block_size - 1) / block_size);
diff.reserve(n / block_size * (block_size - 1) + n % block_size);
}
template<class... Args>
void emplace_back(Args&&... args) {
if (size() % block_size == 0) {
head.emplace_back(std::forward<Args>(args)...);
} else {
value_type v(std::forward<Args>(args)...);
assert(v >= head.back());
assert(v - head.back() <= (value_type)max_diff);
diff.push_back((diff_value_type)(v - head.back()));
}
}
void push_back(const value_type& v) {
if (size() % block_size == 0) {
head.push_back(v);
} else {
assert(v >= head.back());
assert(v - head.back() <= (value_type)max_diff);
diff.push_back(v - head.back());
}
}
void push_back(value_type&& v) {
emplace_back(std::move(v));
}
value_type get(size_t i) const {
if (i % block_size == 0)
return head[i / block_size];
else
return head[i / block_size] +
(value_type)diff[i / block_size * (block_size-1) + i % block_size - 1];
}
value_type operator[](size_t i) const { return get(i); }
value_type front() const { return get(0); }
value_type back() const { return get(size()-1); }
};
#line 7 "include/mtl/succinct/rrr.hpp"
#include <map>
#line 13 "include/mtl/succinct/rrr.hpp"
constexpr unsigned need_bits(uint64_t n) {
return bm::bit_width(n);
}
template<unsigned N>
struct BinomialTable {
static_assert(N < 64,
"Too large N for BinomialTable. N must be less than 64");
using number_type = uint64_t;
using binom_table_type = std::array<std::array<number_type, N+1>, N+1>;
static constexpr binom_table_type make_binomial_table() {
binom_table_type tb{};
tb[0][0] = 1;
for (size_t i = 1; i <= N; i++) {
tb[i][0] = tb[i-1][0];
for (size_t j = 1; j <= i; j++)
tb[i][j] = tb[i-1][j-1] + tb[i-1][j];
}
return tb;
}
static constexpr binom_table_type _binom_tb = make_binomial_table();
static constexpr number_type binom(size_t n, size_t k) {
assert(n <= N and k <= N);
return _binom_tb[n][k];
}
};
template<unsigned N>
constexpr typename BinomialTable<N>::binom_table_type BinomialTable<N>::_binom_tb;
template<class Def>
struct RRRTable {
using def = Def;
static constexpr unsigned s_size = def::s_size;
using s_type = typename def::s_type;
static constexpr unsigned n_bits = def::n_bits;
using binomial_table_type = BinomialTable<s_size>;
using number_type = typename binomial_table_type::number_type;
static constexpr s_type get_int(unsigned n, number_type k, unsigned bits = s_size) {
s_type res = 0;
const auto offset = bits;
s_type mask = ((s_type(1)<<bits)-1);
auto nn = n;
unsigned i = 0;
/*
Binary search time B = ceil(\log_2 w)
Expected length of consecutive zeros Ez = \sum j binom(w-j, nn) / binom(w, nn), j=1..w-nn
Expected length of consecutive ones Eo = \sum j binom(w-j, nn-j) / binom(w, nn), j=1..nn
Approximate simple function from Ez > B to be nn <= min(20, w-1)
Approximate simple function from Eo > B to be nn > min(40, w)
*/
// TODO: When nn > 40, use binary search to find length of consecutive ones
for (; i < offset and nn > 20; i++) {
auto w = s_size - i;
if (nn == w) {
res |= ((s_type(1)<<nn)-1) << i;
return res & mask;
}
if (nn == w-1) {
res |= (((s_type(1)<<w)-1) ^ (s_type(1) << k)) << i;
return res & mask;
}
// Linear search
auto binom = binomial_table_type::binom(w-1, nn);
if (k >= binom) {
res |= s_type(1) << i;
k -= binom;
nn--;
}
}
for (; i < offset and nn > 1; i++) {
auto w = s_size - i;
if (nn == w) {
res |= ((s_type(1)<<nn)-1) << i;
return res & mask;
}
if (nn == w-1) {
res |= (((s_type(1)<<w)-1) ^ (s_type(1) << k)) << i;
return res & mask;
}
// Binary search to find length of consecutive zeros
auto l = i, r = offset+1;
while (l+1<r) {
auto c = l+(r-l)/2;
if (k < binomial_table_type::binom(s_size-c, nn))
l = c;
else
r = c;
}
if (l < offset) {
res |= s_type(1) << l;
k -= binomial_table_type::binom(s_size-l-1, nn);
nn--;
}
i = l;
}
if (nn == 1) {
res |= s_type(1) << (s_size-1-k);
return res & mask;
}
if (nn == 0)
return res;
if (k >= binomial_table_type::binom(s_size-offset-1, nn))
res |= s_type(1) << offset;
return res & ((s_type(1)<<bits)-1);
}
static constexpr bool get_bit(unsigned n, number_type k, unsigned offset) {
auto nn = n;
unsigned i = 0;
/*
Binary search time B = ceil(\log_2 w)
Expected length of consecutive zeros Ez = \sum j binom(w-j, nn) / binom(w, nn), j=1..w-nn
Expected length of consecutive ones Eo = \sum j binom(w-j, nn-j) / binom(w, nn), j=1..nn
Approximate simple function from Ez > B to be nn <= min(20, w-1)
Approximate simple function from Eo > B to be nn > min(40, w)
*/
// TODO: When nn > 40, use binary search to find length of consecutive ones
for (; i < offset and nn > 20; i++) {
auto w = s_size - i;
if (nn == w) {
return 1;
}
if (nn == w-1) {
return offset != i+k;
}
// linear search
auto binom = binomial_table_type::binom(w-1, nn);
if (k >= binom) {
k -= binom;
nn--;
}
}
for (; i < offset and nn > 1; i++) {
auto w = s_size - i;
if (nn == w) {
return 1;
}
if (nn == w-1) {
return offset != i+k;
}
// binary search
auto l = i, r = offset+1;
while (l+1<r) {
auto c = l+(r-l)/2;
if (k < binomial_table_type::binom(s_size-c, nn))
l = c;
else
r = c;
}
if (l < offset) {
k -= binomial_table_type::binom(s_size-l-1, nn);
nn--;
}
i = l;
}
if (nn == 1)
return offset == s_size-1-k;
if (nn == 0)
return 0;
return k >= binomial_table_type::binom(s_size-offset-1, nn);
}
static constexpr number_type get_number_for_popcnt(s_type bitmap, unsigned pc) {
number_type number = 0;
auto m = bitmap;
auto n = pc;
while (m) {
auto i = bm::ctz(m);
number += binomial_table_type::binom(s_size-i-1, n);
n--;
m ^= (s_type(1)<<i);
}
return number;
}
static constexpr number_type number_size(unsigned n) {
return binomial_table_type::binom(s_size, n);
}
static constexpr std::pair<unsigned, number_type> get_pc_and_number(s_type bitmap) {
unsigned pc = bm::popcnt(bitmap);
auto number = pc <= s_size-pc ? get_number_for_popcnt(bitmap, pc)
: (number_size(pc)-1-get_number_for_popcnt(
~bitmap & ((s_type(1)<<s_size)-1), s_size-pc));
return std::make_pair(pc, number);
}
using number_bits_table_type = std::array<unsigned, s_size+1>;
static constexpr number_bits_table_type make_number_bits_table() {
number_bits_table_type tb{};
for (unsigned i = 0; i <= s_size; i++) {
tb[i] = need_bits(number_size(i)-1);
}
return tb;
}
static constexpr number_bits_table_type n_len = make_number_bits_table();
static constexpr unsigned number_bits(unsigned n) {
assert(n <= s_size);
return n_len[n];
}
};
template<class Def>
constexpr typename RRRTable<Def>::number_bits_table_type RRRTable<Def>::n_len;
template<unsigned SSize, class SType>
struct RRRDefinition {
static constexpr unsigned s_size = SSize;
using s_type = SType;
static constexpr unsigned n_bits = need_bits(s_size);
};
/**
* @brief Succinct bit vector in memory of B(n, u) + O(u log log n / log n) bits
* where u is number of bits and n is number of 1s
*/
template<
unsigned SSize = 63,
class SType = uint64_t,
class MapType = std::map<size_t, SType>
>
struct RRR {
using def = RRRDefinition<SSize, SType>;
using s_type = typename def::s_type;
using rrr_table_type = RRRTable<def>;
using map_type = MapType;
using ty_type = TY<size_t>;
map_type s_map;
ty_type heads;
Bitmap bm;
RRR() = default;
void set(size_t i, bool b) {
if (b)
s_map[i/def::s_size] |= (s_type)1<<(i%def::s_size);
else
s_map[i/def::s_size] &= ~((s_type)1<<(i%def::s_size));
}
void build() {
size_t h = 0;
size_t pq = 0;
auto block_count = s_map.empty() ? 0 : std::prev(s_map.end())->first+1;
heads.reserve(block_count);
for (auto qm : s_map) {
auto qidx = qm.first;
auto mask = qm.second;
while (pq < qidx) {
heads.push_back(h);
auto w = def::n_bits;
bm.resize(h+w);
bm.range_set(h, h+w, 0);
h += w;
pq++;
}
heads.push_back(h);
auto np = rrr_table_type::get_pc_and_number(mask);
auto n = np.first;
auto p = np.second;
assert(rrr_table_type::get_int(n, p) == mask);
auto w = def::n_bits + rrr_table_type::number_bits(n);
bm.resize(h+w);
bm.range_set(h, h+def::n_bits, n);
bm.range_set(h+def::n_bits, h+w, p);
assert(bm.range_get(h, h+def::n_bits) == n);
assert(bm.range_get(h+def::n_bits, h+w) == p);
h += w;
pq++;
}
s_map.clear();
}
void move_or_build(RRR&& src) {
*this = std::move(src);
}
void move_or_build(const Bitmap& bm) {
for (size_t i = 0; i < bm.size(); i += def::s_size) {
auto w = bm.range_get(i, std::min(i+def::s_size, bm.size()));
if (w or i+def::s_size >= bm.size()) s_map.emplace(i/def::s_size, w);
}
build();
}
bool get_bit(size_t si, unsigned off) const {
if (si >= heads.size())
return false;
auto a = heads.get(si);
auto b = a+def::n_bits;
auto n = bm.range_get(a, b);
auto p = bm.range_get(b, b+rrr_table_type::number_bits(n));
return rrr_table_type::get_bit(n, p, off);
}
s_type get_mask(size_t si) const {
if (si >= heads.size())
return 0;
auto a = heads.get(si);
auto b = a+def::n_bits;
auto n = bm.range_get(a, b);
auto p = bm.range_get(b, b+rrr_table_type::number_bits(n));
return rrr_table_type::get_int(n, p);
}
uint64_t get_word(size_t si) const {
return get_mask(si);
}
size_t word_size() const {
return heads.size();
}
size_t size() const {
return heads.size() * def::s_size;
}
bool empty() const {
return size() == 0;
}
bool get(size_t i) const {
return get_bit(i/def::s_size, i%def::s_size);
}
};
#line 5 "include/mtl/succinct/traits.hpp"
template<class T>
struct RankSelectTraits : std::false_type {};
template<>
struct RankSelectTraits<Bitmap> {
using rank_select_type = BV<Bitmap, 64>;
};
template<unsigned SSize, class SType, class MapType>
struct RankSelectTraits<RRR<SSize, SType, MapType>> {
using rank_select_type = BV<RRR<SSize, SType, MapType>, SSize>;
};
#line 10 "include/mtl/succinct/bit_vector.hpp"
struct BitVector {
using bitmap_type = Bitmap;
bitmap_type bm;
using rs_type = typename RankSelectTraits<bitmap_type>::rank_select_type;
rs_type rs_support;
// std::vector<uint64_t> _r, _s, _zs;
BitVector() = default;
explicit BitVector(size_t size) : bm(size) {}
BitVector(size_t size, bool bit) : bm(size, bit) {}
BitVector(const BitVector& rhs) : bm(rhs.bm), rs_support(rhs.rs_support) {
rs_support.set_ptr(&bm);
}
BitVector& operator=(const BitVector& rhs) {
bm = rhs.bm;
rs_support = rhs.rs_support;
rs_support.set_ptr(&bm);
return *this;
}
BitVector(BitVector&& rhs) noexcept :
bm(std::move(rhs.bm)),
rs_support(std::move(rhs.rs_support)) {
rs_support.set_ptr(&bm);
}
BitVector& operator=(BitVector&& rhs) noexcept {
bm = std::move(rhs.bm);
rs_support = std::move(rhs.rs_support);
rs_support.set_ptr(&bm);
return *this;
}
template<typename It>
BitVector(It begin, It end) : bm(begin, end) {
build();
}
size_t size() const { return bm.size(); }
bool empty() const { return bm.empty(); }
void push_back(bool bit) { bm.push_back(bit); }
void resize(size_t new_size, bool bit = false) { bm.resize(new_size, bit); }
void assign(size_t new_size, bool bit) { bm.assign(new_size, bit); }
void reserve(size_t reserved_size) { bm.reserve(reserved_size); }
bitmap_type& bitmap() { return bm; }
const bitmap_type& bitmap() const { return bm; }
bitmap_type::const_reference operator[](size_t i) const { return bm[i]; }
bitmap_type::reference operator[](size_t i) { return bm[i]; }
bitmap_type::const_iterator begin() const { return bm.begin(); }
bitmap_type::const_iterator end() const { return bm.end(); }
bitmap_type::iterator begin() { return bm.begin(); }
bitmap_type::iterator end() { return bm.end(); }
bitmap_type::const_iterator cbegin() const { return bm.cbegin(); }
bitmap_type::const_iterator cend() const { return bm.cend(); }
void build() {
rs_support.build(&bm);
}
inline size_t rank(size_t i) const {
return rs_support.rank1(i);
}
size_t rank1(size_t i) const {
return rs_support.rank1(i);
}
size_t rank0(size_t i) const {
return rs_support.rank0(i);
}
template<bool B>
size_t select(size_t n) const {
return rs_support.select<B>(n);
}
size_t select1(size_t n) const {
return rs_support.select<1>(n);
}
size_t select0(size_t n) const {
return rs_support.select<0>(n);
}
};
#line 5 "include/mtl/sparse_table.hpp"
template <class T, T (*op)(T, T)>
class SparseTable {
public:
using value_type = T;
private:
size_t size_;
size_t log_n_;
std::vector<std::vector<value_type>> table_;
public:
SparseTable() = default;
template <class Iter>
SparseTable(Iter begin, Iter end) :
size_(std::distance(begin, end)),
log_n_(63-bm::clz(size_)),
table_(log_n_+1, std::vector<value_type>(size_))
{
std::copy(begin, end, table_[0].begin());
for (size_t log_n = 1; log_n <= log_n_; log_n++) {
size_t width = 1ull<<log_n;
for (size_t i = 0; i + width <= size_; i++) {
table_[log_n][i] = op(table_[log_n-1][i],
table_[log_n-1][i+width/2]);
}
}
}
value_type query(size_t l, size_t r) const {
size_t p = 63-bm::clz(r-l);
return op(table_[p][l], table_[p][r-(1ull<<p)]);
}
};
#line 7 "include/mtl/range_minimum_query.hpp"
#include <stack>
#include <tuple>
#line 10 "include/mtl/range_minimum_query.hpp"
#include <bit>
#ifndef MTL_ARRAY_SET_CONSTEXPR
#if __cplusplus >= 201703L
#define MTL_ARRAY_SET_CONSTEXPR constexpr
#else
#define MTL_ARRAY_SET_CONSTEXPR
#endif
#endif
namespace rmq {
constexpr int table_width = 8;
constexpr size_t table_size = 1u << table_width;
struct make_rmq_table {
std::array<uint8_t, table_size> idx;
std::array<int8_t, table_size> val;
MTL_ARRAY_SET_CONSTEXPR
make_rmq_table() : idx(), val() {
for (unsigned int mask = 0; mask < table_size; mask++) {
uint8_t argmin = 0;
int8_t min_s = table_width+1, sum = 0;
for (uint8_t i = 0; i < table_width; i++) {
if ((mask>>i) & 1) sum++;
else sum--;
if (sum < min_s) {
min_s = sum;
argmin = i;
}
}
idx[mask] = argmin;
val[mask] = min_s;
}
}
};
} // namespace rmq
MTL_ARRAY_SET_CONSTEXPR
rmq::make_rmq_table rmq_tb;
#ifndef MTL_PAIR_CONSTEXPR
#if __cplusplus >= 201402L
#define MTL_PAIR_CONSTEXPR constexpr
#else
#define MTL_PAIR_CONSTEXPR
#endif
#endif
namespace rmq {
// constexpr int block_width = 8;
constexpr int block_width = 64;
MTL_PAIR_CONSTEXPR
std::pair<unsigned, int> rmq64(uint64_t mask) {
// Calc E[i-1] as ( rank1_B(i) * 2 - i ) { forall i| i % 8 = 0 }
auto pos_e8 = bm::popcnt_e8(mask) * 2;
auto cpos_e8 = pos_e8 * 0x0101010101010100ull;
constexpr auto cneg_e8 = 8ull * 0x0706050403020100ull;
constexpr int offset = 64; // to keep values non-negative
auto e_e8 = offset * 0x0101010101010101ull + cpos_e8 - cneg_e8;
unsigned argmin = 0;
int min_s = block_width+1;
// int sum = 0;
constexpr uint64_t table_mask = (1ull << table_width) - 1;
for (unsigned bi = 0; bi < block_width; bi += table_width) {
auto submask = (mask >> bi) & table_mask;
auto estart = (int)((e_e8 >> bi) & table_mask) - offset;
// assert(sum == estart);
auto s = rmq_tb.val[submask] + estart;
if (s < min_s) {
min_s = s;
argmin = rmq_tb.idx[submask] + bi;
}
// int subsum = bm::popcnt(submask) * 2 - table_width;
// sum += subsum;
}
return std::make_pair(argmin, min_s);
}
} // namespace rmq
template<class T>
struct DecaltTree {
static constexpr size_t null_idx = -1;
struct Node {
size_t p, l, r;
};
size_t root_;
std::vector<Node> nodes_;
DecaltTree() : root_(null_idx) {}
template<class It>
explicit DecaltTree(It begin, It end) : DecaltTree() {
nodes_.reserve(std::distance(begin, end));
std::vector<T> a;
for (auto it = begin; it != end; ++it) {
auto val = *it;
a.push_back(val);
if (nodes_.empty()) {
nodes_.push_back({null_idx, null_idx, null_idx});
root_ = 0;
continue;
}
auto u = nodes_.size()-1;
auto v = nodes_.size();
while (u != null_idx and a[u] > a[v]) {
u = nodes_[u].p;
}
if (u == null_idx) {
nodes_.push_back({null_idx, root_, null_idx});
nodes_[root_].p = v;
root_ = v;
} else {
auto ur = nodes_[u].r;
nodes_.push_back({u, ur, null_idx});
if (ur != null_idx)
nodes_[ur].p = v;
nodes_[u].r = v;
}
}
}
size_t size() const {
return nodes_.size();
}
};
template<class T>
constexpr size_t DecaltTree<T>::null_idx;
template<class T, class InFn, class PostFn>
void traverse_right_path_to_children(const DecaltTree<T>& tree, InFn in_fn, PostFn post_fn) {
std::stack<std::tuple<size_t, size_t, bool>> st; // (u, left_child, is_inorder)
st.emplace(DecaltTree<T>::null_idx, DecaltTree<T>::null_idx, false);
st.emplace(DecaltTree<T>::null_idx, tree.root_, true);
std::vector<size_t> c;
while (!st.empty()) {
// auto [u,lc,in] = st.top();
auto u = std::get<0>(st.top());
auto lc = std::get<1>(st.top());
auto in = std::get<2>(st.top());
st.pop();
if (in) {
c.clear();
auto v = lc;
while (v != DecaltTree<T>::null_idx) {
c.push_back(v);
v = tree.nodes_[v].r;
}
for (auto it = c.rbegin(); it != c.rend(); it++) {
auto v = *it;
st.emplace(v, DecaltTree<T>::null_idx, false);
st.emplace(v, tree.nodes_[v].l, true);
}
in_fn(u);
} else {
post_fn(u);
}
}
};
template<class T, unsigned RecursionHeight>
class RmqToLca;
template<unsigned RecursionHeight>
class LcaToRmq;
template<class T>
T _fn_min(T l, T r) {
return std::min(l, r);
}
template<class T, unsigned RecursionHeight = 3>
class RmqToLca {
static constexpr size_t minimum_rmq_size = 1u<<3;
using st_index_type = size_t;
private:
size_t size_;
using st_unit_type = std::pair<T, st_index_type>;
SparseTable<st_unit_type, _fn_min<st_unit_type>> st_;
LcaToRmq<RecursionHeight> lca_a_;
public:
RmqToLca() = default;
template<class It>
RmqToLca(It begin, It end) : size_(std::distance(begin, end)) {
// std::cerr<<RecursionHeight<<' '<<size_<<std::endl;
if (size_ <= minimum_rmq_size) {
std::vector<std::pair<T, st_index_type>> st_data(size_);
auto it = begin;
for (size_t i = 0; i < size_; i++) {
st_data[i] = std::make_pair(*(it++), i);
}
st_ = decltype(st_)(st_data.begin(), st_data.end());
} else {
lca_a_ = decltype(lca_a_)(DecaltTree<T>(begin, end));
}
}
size_t rmq(size_t l, size_t r) const {
if (l >= r) {
throw std::invalid_argument("r-l must be positive");
}
if (size() <= minimum_rmq_size)
return st_.query(l, r).second;
else
return lca_a_.lca(l, r-1);
}
size_t size() const {
return size_;
}
};
template<class T>
class RmqToLca<T, 0> {
using st_index_type = size_t;
private:
size_t size_;
using st_unit_type = std::pair<T, st_index_type>;
SparseTable<st_unit_type, _fn_min<st_unit_type>> st_;
public:
RmqToLca() = default;
template<class It>
RmqToLca(It begin, It end) : size_(std::distance(begin, end)) {
std::vector<std::pair<T, st_index_type>> st_data(size_);
auto it = begin;
for (size_t i = 0; i < size_; i++) {
st_data[i] = std::make_pair(*(it++), i);
}
st_ = decltype(st_)(st_data.begin(), st_data.end());
}
size_t rmq(size_t l, size_t r) const {
return st_.query(l, r).second;
}
size_t size() const {
return size_;
}
};
template<unsigned RecursionHeight>
class LcaToRmq {
private:
// std::vector<size_t> d_;
// std::vector<size_t> l_;
BitVector b_;
RmqToLca<size_t, RecursionHeight - 1> rmq_a_;
public:
LcaToRmq() = default;
template<class U>
LcaToRmq(const DecaltTree<U>& decalt_tree)
// : d_(decalt_tree.size(), -1), l_(2*decalt_tree.size(), -1)
{
// std::vector<bool> de(2*decalt_tree.size());
b_.resize(2*(decalt_tree.size()+1));
// std::vector<size_t> f(decalt_tree.size(), -1);
size_t t = 0;
traverse_right_path_to_children(decalt_tree,
[&](size_t u) {
// d_[u] = t;
// e.push_back(h);
b_[t] = 1;
// l_[t] = -1; // dummy
t++;
},
[&](size_t u) {
// f[u] = t;
// e.push_back(h-1);
b_[t] = 0;
// l_[t] = decalt_tree.nodes_[u].p;
t++;
});
// Construcr from normal decalt-tree
// std::stack<std::pair<size_t, bool>> st;
// st.emplace(decalt_tree.root_, false);
// st.emplace(decalt_tree.root_, true);
// while (!st.empty()) {
// auto [u, is_in] = st.top(); st.pop();
// if (is_in) {
// d_[u] = t;
// // e.push_back(h);
// de[t] = 1;
// // l_[t] = -1; // dummy
// auto cl = decalt_tree.nodes_[u].l, cr = decalt_tree.nodes_[u].r;
// if (cr != DecaltTree<U>::null_idx) {
// st.emplace(cr, false);
// st.emplace(cr, true);
// }
// if (cl != DecaltTree<U>::null_idx) {
// st.emplace(cl, false);
// st.emplace(cl, true);
// }
// } else {
// // f[u] = t;
// // e.push_back(h-1);
// de[t] = 0;
// l_[t] = decalt_tree.nodes_[u].p;
// }
// t++;
// }
b_.build();
auto num_blocks = (b_.size() + rmq::block_width - 1) / rmq::block_width;
if (num_blocks >= 3) {
std::vector<size_t> a(num_blocks);
size_t block_sum = 0;
size_t ei = 0, bi = 0;
while (ei + rmq::block_width < b_.size()) {
auto width = std::min(rmq::block_width, (int)(b_.size()-ei));
auto mask = b_.bitmap().range_get(ei, ei+width);
if (width < rmq::block_width)
mask |= ((1ull<<(rmq::block_width-width))-1) << width;
ei += rmq::block_width;
// a[bi] = (long long) rmq_tb.val[mask] + block_sum;
a[bi] = (long long) rmq::rmq64(mask).second + block_sum;
block_sum += bm::popcnt(mask) * 2;
block_sum -= rmq::block_width;
bi++;
}
rmq_a_ = decltype(rmq_a_)(a.begin()+1, a.end()-1);
}
}
size_t get_e(size_t i) const {
return b_.rank1(i+1) * 2 - (i+1);
}
size_t lca(size_t x, size_t y) const {
if (x == y) return x;
auto xx = b_.select0(x);
auto yy = b_.select0(y);
// if (d_[x] > d_[y]) std::swap(x, y);
if (xx > yy) std::swap(xx, yy);
// size_t i = d_[x] / rmq::block_width;
// size_t j = d_[y] / rmq::block_width;
size_t i = xx / rmq::block_width;
size_t j = yy / rmq::block_width;
size_t m;
size_t min_e;
{ // block i
auto r = std::min(yy+1, (i+1)*rmq::block_width);
auto mask = b_.bitmap().range_get(xx, r);
auto dist = r - xx;
auto rem = rmq::block_width - dist;
if (rem)
mask |= ((1ull<<rem)-1) << dist;
// auto idx = rmq_tb.idx[mask] + d_[x];
auto idx = rmq::rmq64(mask).first + xx;
auto e = get_e(idx);
m = idx;
min_e = e;
}
if (i+2 <= j) { // block i+1...j-1
auto k = rmq_a_.rmq(i+1 - 1, j - 1) + 1; // -1 means ignoring i={0,num_block-1}
auto mask = b_.bitmap().range_get(k*rmq::block_width, (k+1)*rmq::block_width);
// auto idx = rmq_tb.idx[mask] + k*rmq::block_width;
auto idx = rmq::rmq64(mask).first + k*rmq::block_width;
auto e = get_e(idx);
if (e < min_e) {
min_e = e;
m = idx;
}
}
if (i < j) { // block j
auto l = j*rmq::block_width;
auto mask = b_.bitmap().range_get(l, yy+1);
auto dist = yy+1 - l;
auto rem = rmq::block_width - dist;
if (rem)
mask |= ((1ull<<rem)-1) << dist;
// auto idx = rmq_tb.idx[mask] + j*rmq::block_width;
auto idx = rmq::rmq64(mask).first + j*rmq::block_width;
auto e = get_e(idx);
if (e < min_e) {
min_e = e;
m = idx;
}
}
// auto ret = m == d_[x] ? x : l_[m];
auto ret = m == xx ? x : b_.rank0(m);
// std::cerr<<"d[x] d[y] rmq_e(d[x],d[y]) "<<d_[x]<<' '<<d_[y]<<' '<<m<<std::endl;
// std::cerr<<"x y lca_t(x,y) "<<x<<' '<<y<<' '<<ret<<std::endl;
// std::cerr<<"E[d[x]] E[m] "<<get_e(d_[x])<<' '<<get_e(m)<<std::endl;
// if (m == d_[x]) {
// } else {
// assert(get_e(m) < get_e(d_[x]));
// assert(l_[m] != x);
// }
return ret;
}
static bool test_right_path_to_children_construction() {
std::vector<int> A{2,4,3,5,1,8,6,7,9};
std::vector<bool> B{1,1,1,0,1,1,0,0,1,0,0,1,1,0,0,1,0,1,0,0};
DecaltTree<int> tree(A.begin(), A.end());
LcaToRmq ltr(tree);
bool ok = B.size()==ltr.b_.size();
for (size_t i = 0; i < B.size(); i++) {
ok &= B[i]==ltr.b_[i];
}
if (!ok) {
std::cerr<<B.size()<<' '<<ltr.b_.size()<<std::endl;
for (size_t i = 0; i < B.size(); i++) {
std::cerr<<B[i]<<' '<<ltr.b_[i]<<std::endl;
}
}
return ok;
}
};
template<class T>
using Rmq = RmqToLca<T>;
#line 5 "test/yosupo/static_rmq-constant_rmq.test.cpp"
using namespace std;
int main() {
int n,q; cin>>n>>q;
vector<int> A(n);
for (int i = 0; i < n; i++) cin>>A[i];
Rmq<int> st(A.begin(), A.end());
while (q--) {
int l,r; cin>>l>>r;
auto min_idx = st.rmq(l,r);
// if (!(l <= min_idx and min_idx < r)) {
// std::cerr<<"l r min_idx "<<l<<' '<<r<<' '<<min_idx<<std::endl;
// }
// assert(l <= min_idx and min_idx < r);
cout<<A[min_idx]<<endl;
}
}
Test cases
| Env | Name | Status | Elapsed | Memory |
|---|---|---|---|---|
| g++ | example_00 |
AC |
5 ms | 3 MB |
| g++ | max_random_00 |
AC |
1337 ms | 19 MB |
| g++ | max_random_01 |
AC |
1445 ms | 19 MB |
| g++ | max_random_02 |
AC |
1436 ms | 19 MB |
| g++ | max_random_03 |
AC |
1193 ms | 19 MB |
| g++ | max_random_04 |
AC |
1269 ms | 19 MB |
| g++ | random_00 |
AC |
1026 ms | 16 MB |
| g++ | random_01 |
AC |
1001 ms | 18 MB |
| g++ | random_02 |
AC |
794 ms | 5 MB |
| g++ | random_03 |
AC |
200 ms | 17 MB |
| g++ | random_04 |
AC |
298 ms | 13 MB |
| g++ | small_00 |
AC |
7 ms | 3 MB |
| g++ | small_01 |
AC |
7 ms | 3 MB |
| g++ | small_02 |
AC |
6 ms | 3 MB |
| g++ | small_03 |
AC |
6 ms | 3 MB |
| g++ | small_04 |
AC |
6 ms | 3 MB |
| g++ | small_05 |
AC |
7 ms | 3 MB |
| g++ | small_06 |
AC |
7 ms | 3 MB |
| g++ | small_07 |
AC |
6 ms | 3 MB |
| g++ | small_08 |
AC |
7 ms | 3 MB |
| g++ | small_09 |
AC |
7 ms | 3 MB |
| g++ | small_values_00 |
AC |
1071 ms | 20 MB |
| g++ | small_width_query_00 |
AC |
1013 ms | 19 MB |
| g++ | small_width_query_01 |
AC |
1025 ms | 19 MB |
| g++ | small_width_query_02 |
AC |
1001 ms | 19 MB |
| g++ | small_width_query_03 |
AC |
1063 ms | 19 MB |
| g++ | small_width_query_04 |
AC |
1020 ms | 19 MB |
| clang++ | example_00 |
AC |
6 ms | 3 MB |
| clang++ | max_random_00 |
AC |
1382 ms | 19 MB |
| clang++ | max_random_01 |
AC |
1195 ms | 19 MB |
| clang++ | max_random_02 |
AC |
1179 ms | 19 MB |
| clang++ | max_random_03 |
AC |
1170 ms | 19 MB |
| clang++ | max_random_04 |
AC |
1194 ms | 19 MB |
| clang++ | random_00 |
AC |
949 ms | 16 MB |
| clang++ | random_01 |
AC |
975 ms | 18 MB |
| clang++ | random_02 |
AC |
735 ms | 5 MB |
| clang++ | random_03 |
AC |
196 ms | 17 MB |
| clang++ | random_04 |
AC |
289 ms | 13 MB |
| clang++ | small_00 |
AC |
7 ms | 3 MB |
| clang++ | small_01 |
AC |
7 ms | 3 MB |
| clang++ | small_02 |
AC |
6 ms | 3 MB |
| clang++ | small_03 |
AC |
7 ms | 3 MB |
| clang++ | small_04 |
AC |
7 ms | 3 MB |
| clang++ | small_05 |
AC |
7 ms | 3 MB |
| clang++ | small_06 |
AC |
7 ms | 3 MB |
| clang++ | small_07 |
AC |
6 ms | 3 MB |
| clang++ | small_08 |
AC |
7 ms | 3 MB |
| clang++ | small_09 |
AC |
7 ms | 3 MB |
| clang++ | small_values_00 |
AC |
1106 ms | 20 MB |
| clang++ | small_width_query_00 |
AC |
1021 ms | 19 MB |
| clang++ | small_width_query_01 |
AC |
990 ms | 19 MB |
| clang++ | small_width_query_02 |
AC |
1119 ms | 19 MB |
| clang++ | small_width_query_03 |
AC |
1096 ms | 19 MB |
| clang++ | small_width_query_04 |
AC |
1073 ms | 19 MB |