cp-library
競技プログラミング用 C++ ライブラリ
区間加算・区間最小値
data_structure/range_add_range_min.hpp · GitHub で見る
共通ページ
整数列の区間加算・区間最小値・一点代入に対応します。T の既定値は std::int64_t、value_type は T です。
#include "lib/data_structure/range_add_range_min.hpp"
#include <iostream>
int main() {
RangeAddRangeMin<> values(std::vector<std::int64_t>{3, 1, 5});
values.add(0, 2, 4);
std::cout << values.prod(0, 3) << '\n';
values.set(2, -1);
std::cout << values.all_min() << '\n';
}
出力は次のとおりです。
5
-1
| 操作 | 内容・返り値 | 計算量 |
|---|---|---|
RangeAddRangeMin<T>() |
空の RangeAddRangeMin<T> を構築 |
\(O(1)\) |
RangeAddRangeMin<T>(values) |
const std::vector<T>& の各値から構築。入力は変更しない |
\(O(n)\) |
RangeAddRangeMin<T>(n,value=0) |
int n 個の要素を T value で初期化 |
\(O(n)\) |
| コピー構築／コピー代入 | 独立した内容を複製。代入の返り値は RangeAddRangeMin&
|
\(O(n)\) |
| 移動構築／移動代入 | 内容を移し、移動元を空にする。代入の返り値は RangeAddRangeMin&
|
\(O(1)\) |
build(values) |
const std::vector<T>& から作り直す。返り値は void
|
\(O(n)\) |
size() / empty()
|
要素数を int、空判定を bool で返す |
\(O(1)\) |
add(l,r,value) / apply(l,r,value)
|
int l,r の半開区間 [l,r) に T value を加算。返り値は void
|
\(O(\log n)\) |
prod(l,r) / min(l,r)
|
int l,r の半開区間 [l,r) の最小値を T で返す |
\(O(\log n)\) |
all_prod() / all_min()
|
全要素の最小値を T で返す |
\(O(1)\) |
get(p) |
int p の値を T で返す |
\(O(\log n)\) |
set(p,value) |
int p に T value を代入。返り値は void
|
\(O(\log n)\) |
values() |
現在の全要素を添字順の std::vector<T> で返す |
\(O(n)\) |
memory_usage() |
内部配列が確保したバイト数を std::size_t で返す |
\(O(1)\) |
swap(other) / swap(a,b)
|
同じ型の構造同士の内容を交換。返り値は void
|
\(O(1)\) |
T は 64 bit 以下の標準の符号付き整数型です。要素・代入値・加算量と、各更新後のすべての要素が T の範囲に収まるように使ってください。負の値・負の加算・型の最小値と最大値に対応し。要素の最大値と最小値の差が T の範囲を超えていても扱えます。初期値の重複もそのまま保持します。
これらの値が signed 32 bit に収まる場合は、RangeAddRangeMin<std::int32_t> を指定できます。この場合も、要素の最大値と最小値の差を signed 32 bit に収める必要はありません。
区間は 0 <= l <= r <= size()、位置は 0 <= p < size()、長さは 0 <= n <= INT_MAX です。空区間への加算は何もせず、空区間・空の構造の最小値は std::numeric_limits<T>::max() を返します。この値を通常の要素として格納することもできます。get・set には存在する位置を指定します。空の初期配列・build にも対応します。
取得操作は const オブジェクトから呼べ、内部状態を変更しません。コピーは独立した構造を作り、移動元は再利用できる空の構造になります。
参考: Library Checker の問題、参考実装。
構築・使用空間・values は \(O(n)\)、更新・区間最小値・一点の取得や代入は最悪 \(O(\log n)\) 時間です。全区間への加算・全区間の最小値取得は \(O(1)\) です。保持している全体最小の位置を含むと確認できる区間も \(O(1)\) で取得します。全要素を同じ値で構築し、以降の更新を全区間への加算に限る場合、どの非空区間の最小値も型によらず \(O(1)\) で取得します。
依存ライブラリ
コード
#ifndef RANGE_ADD_RANGE_MIN_HPP
#define RANGE_ADD_RANGE_MIN_HPP
#include "../components/aligned_allocator.hpp"
#include "../components/range_add_min_node.hpp"
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>
template<class T = std::int64_t> class RangeAddRangeMin {
static_assert(std::is_integral_v<T> && std::is_signed_v<T> && sizeof(T) <= 8);
using U = std::make_unsigned_t<T>;
using Node = range_add_min_detail::Node<T>;
static constexpr unsigned branch = 8, bits = 3;
static constexpr T infinity = std::numeric_limits<T>::max();
static constexpr U umax = std::numeric_limits<U>::max();
static constexpr U limit_ = U(infinity) / 3;
std::vector<U, AlignedAllocator<U>> data_;
std::array<std::size_t, (sizeof(int) * 8 + bits - 1) / bits + 1> offsets_{}, counts_{};
int n_ = 0, minimum_pos_ = -1;
unsigned height_ = 0;
std::size_t width_ = 1;
T root_ = infinity;
U bound_ = 0;
static T added(T value, U delta) { return std::bit_cast<T>(U(U(value) + delta)); }
unsigned block_count(unsigned level, std::size_t index) const { return unsigned(std::min<std::size_t>(branch, counts_[level] - index * branch)); }
template<bool Narrow>
void propagate(unsigned level, std::size_t index, U change, bool negative) {
for (; level < height_; ++level, index >>= bits) {
if (!change) return;
std::size_t block = index >> bits;
change = Node::template change_one<Narrow>(data_.data() + offsets_[level] + block * branch, block_count(level, block), index & (branch - 1), change, negative);
}
root_ = added(root_, change);
}
template<bool Narrow>
void update(std::size_t l, std::size_t r, U delta, bool negative) {
--r;
std::size_t a = l >> bits, b = r >> bits;
unsigned first = unsigned(l & (branch - 1)), last = unsigned(r & (branch - 1));
if (a == b) {
U change = first == last ? Node::template change_one<Narrow>(data_.data() + a * branch, block_count(0, a), first, delta, negative)
: Node::template normalize<Narrow>(data_.data() + a * branch, block_count(0, a), negative, first, last + 1, delta);
propagate<Narrow>(1, a, change, negative);
return;
}
auto ends = Node::template normalize_boundaries<Narrow>(data_.data() + a * branch, data_.data() + b * branch, block_count(0, b), negative, first, last, delta, delta, delta);
U left = ends.first, right = ends.second;
for (unsigned level = 1;; ++level) {
l >>= bits;
r >>= bits;
first = unsigned(l & (branch - 1));
last = unsigned(r & (branch - 1));
a = l >> bits;
b = r >> bits;
U *values = data_.data() + offsets_[level];
if (a == b) {
U change;
if (first + 1 == last) {
change = Node::template change_one<Narrow>(values + a * branch, block_count(level, a), first, left, negative);
change += Node::template change_one<Narrow>(values + a * branch, block_count(level, a), last, right, negative);
} else change = Node::template normalize<Narrow>(values + a * branch, block_count(level, a), negative, first + 1, last, delta, first, left, last, right);
propagate<Narrow>(level + 1, a, change, negative);
return;
}
if (first + 1 < branch && last) {
auto ends = Node::template normalize_boundaries<Narrow>(values + a * branch, values + b * branch, block_count(level, b), negative, first, last, delta, left, right);
left = ends.first, right = ends.second;
} else {
left = first + 1 == branch ? Node::template change_one<Narrow>(values + a * branch, branch, first, left, negative)
: Node::template normalize<Narrow>(values + a * branch, branch, negative, first + 1, branch, delta, first, left);
right = !last ? Node::template change_one<Narrow>(values + b * branch, block_count(level, b), 0, right, negative)
: Node::template normalize<Narrow>(values + b * branch, block_count(level, b), negative, 0, last, delta, last, right);
}
}
}
U restore(unsigned level, std::size_t index, U result) const {
for (; level < height_; ++level, index >>= bits) result += data_[offsets_[level] + index];
return result;
}
template<bool Narrow>
U query(std::size_t l, std::size_t r) const {
if constexpr (sizeof(T) < 8) if (!bound_) return 0;
--r;
std::size_t a = l >> bits, b = r >> bits;
if (a == b) {
if (l == r) return restore(0, l, 0);
return restore(1, a, Node::template minimum<Narrow>(data_.data() + a * branch, l & (branch - 1), (r & (branch - 1)) + 1));
}
U left = Node::template minimum<Narrow>(data_.data() + a * branch, l & (branch - 1), branch);
U right = Node::template minimum<Narrow>(data_.data() + b * branch, 0, (r & (branch - 1)) + 1);
for (unsigned level = 1;; ++level) {
l >>= bits;
r >>= bits;
left += data_[offsets_[level] + l];
right += data_[offsets_[level] + r];
unsigned first = unsigned(l & (branch - 1)), last = unsigned(r & (branch - 1));
a = l >> bits;
b = r >> bits;
const U *values = data_.data() + offsets_[level];
if (a == b) {
U result = std::min(left, right);
if (first + 1 < last) result = std::min(result, Node::template minimum<Narrow>(values + a * branch, first + 1, last));
return restore(level + 1, a, result);
}
if (first + 1 < branch) left = std::min(left, Node::template minimum<Narrow>(values + a * branch, first + 1, branch));
if (last) right = std::min(right, Node::template minimum<Narrow>(values + b * branch, 0, last));
}
}
#if defined(__AVX2__) && !defined(__AVX512F__) && defined(__x86_64__)
static __m256i query_block(const U* values, unsigned first, unsigned last) {
return Node::template minimum_vector<true>(values, first, last, 2 * limit_);
}
U query_vector(std::size_t l, std::size_t r) const {
--r;
std::size_t a = l >> bits, b = r >> bits;
if (a == b) {
if (l == r) return restore(0, l, 0);
auto value = query_block(data_.data() + a * branch, l & (branch - 1), (r & (branch - 1)) + 1);
U carry = restore(1, a, 0);
return Node::reduce_min(value) + carry;
}
auto left = query_block(data_.data() + a * branch, l & (branch - 1), branch);
auto right = query_block(data_.data() + b * branch, 0, (r & (branch - 1)) + 1);
for (unsigned level = 1;; ++level) {
l >>= bits;
r >>= bits;
left = _mm256_add_epi64(left, _mm256_set1_epi64x(std::int64_t(data_[offsets_[level] + l])));
right = _mm256_add_epi64(right, _mm256_set1_epi64x(std::int64_t(data_[offsets_[level] + r])));
unsigned first = unsigned(l & (branch - 1)), last = unsigned(r & (branch - 1));
a = l >> bits;
b = r >> bits;
const U* values = data_.data() + offsets_[level];
if (a == b) {
auto result = Node::min_signed(left, right);
if (first + 1 < last) result = Node::min_signed(result, query_block(values + a * branch, first + 1, last));
U carry = restore(level + 1, a, 0);
return Node::reduce_min(result) + carry;
}
if (first + 1 < branch) left = Node::min_signed(left, query_block(values + a * branch, first + 1, branch));
if (last) right = Node::min_signed(right, query_block(values + b * branch, 0, last));
}
}
#endif
template<bool Narrow>
U assign(unsigned level, std::size_t index, std::size_t pos, U delta, bool negative) {
unsigned child = unsigned((pos >> (bits * level)) & (branch - 1));
U change = level ? assign<Narrow>(level - 1, index * branch + child, pos, delta, negative) : delta;
unsigned count = unsigned(std::min<std::size_t>(branch, counts_[level] - index * branch));
return Node::template change_one<Narrow>(data_.data() + offsets_[level] + index * branch, count, child, change, negative);
}
void collect(unsigned level, std::size_t index, std::size_t start, std::size_t width, U base, std::vector<T> &result) const {
const U *values = data_.data() + offsets_[level] + index * branch;
if (!level) {
unsigned count = unsigned(std::min<std::size_t>(branch, std::size_t(n_) - start));
Node::materialize(values, result.data() + start, count, base);
return;
}
std::size_t part = width / branch;
for (unsigned i = 0; i < branch && start + i * part < std::size_t(n_); ++i)
collect(level - 1, index * branch + i, start + i * part, part, U(base + values[i]), result);
}
void padding(U value) {
for (unsigned level = 0; level < height_; ++level) {
std::size_t count = counts_[level], remainder = count & (branch - 1);
if (remainder) {
U* first = data_.data() + offsets_[level] + count;
std::fill(first, first + branch - remainder, value);
}
}
}
void track(U amount) {
if constexpr (sizeof(T) == 8) {
bool narrow = bound_ < limit_;
bound_ = narrow && amount < limit_ - bound_ ? U(bound_ + amount) : umax;
if (narrow && bound_ == umax) padding(umax);
} else bound_ = 1;
}
void allocate(int n, U value) {
n_ = n;
if (!n) return;
std::size_t total = 0, count = n;
for (unsigned level = 0;; ++level) {
std::size_t groups = (count + branch - 1) / branch;
offsets_[level] = total;
counts_[level] = count;
total += groups * branch;
if (width_ > std::numeric_limits<std::size_t>::max() / branch) throw std::length_error("RangeAddRangeMin size");
width_ *= branch;
if (groups == 1) { height_ = level + 1; break; }
count = groups;
}
data_.resize(total, value);
}
void check([[maybe_unused]] int l, [[maybe_unused]] int r) const { assert(0 <= l && l <= r && r <= n_); }
public:
using value_type = T;
RangeAddRangeMin() = default;
explicit RangeAddRangeMin(int n, T value = 0) {
assert(n >= 0);
allocate(n, 0);
if (n) { root_ = value; minimum_pos_ = n / 2; padding(sizeof(T) == 8 ? 2 * limit_ : umax); }
}
explicit RangeAddRangeMin(const std::vector<T> &values) { build(values); }
RangeAddRangeMin(const RangeAddRangeMin &) = default;
RangeAddRangeMin(RangeAddRangeMin &&other) noexcept { swap(other); }
RangeAddRangeMin &operator=(RangeAddRangeMin other) noexcept { swap(other); return *this; }
void build(const std::vector<T> &values) {
assert(values.size() <= std::size_t(std::numeric_limits<int>::max()));
auto extremes = std::minmax_element(values.begin(), values.end());
if (!values.empty() && *extremes.first == *extremes.second) {
RangeAddRangeMin next(int(values.size()), *extremes.first);
swap(next);
return;
}
RangeAddRangeMin next;
next.allocate(int(values.size()), umax);
if (!values.empty()) {
std::copy(values.begin(), values.end(), next.data_.begin());
for (unsigned level = 0; level < next.height_; ++level) {
std::size_t groups = (next.counts_[level] + branch - 1) / branch;
for (std::size_t group = 0; group < groups; ++group) {
T minimum = Node::build(next.data_.data() + next.offsets_[level] + group * branch, next.block_count(level, group));
if (level + 1 == next.height_) next.root_ = minimum;
else next.data_[next.offsets_[level + 1] + group] = U(minimum);
}
}
next.minimum_pos_ = values[values.size() / 2] == next.root_ ? int(values.size() / 2) : int(extremes.first - values.begin());
next.bound_ = U(U(*extremes.second) - U(next.root_));
if constexpr (sizeof(T) == 8) if (next.bound_ < limit_) next.padding(2 * limit_);
}
swap(next);
}
int size() const { return n_; }
bool empty() const { return !n_; }
void add(int l, int r, T value) {
check(l, r);
if (l == r || !value) return;
if (l == 0 && r == n_) { root_ = added(root_, U(value)); return; }
T candidate = root_;
if (l <= minimum_pos_ && minimum_pos_ < r) candidate = added(root_, U(value));
if constexpr (sizeof(T) == 8) {
track(value < 0 ? U(0) - U(value) : U(value));
if (bound_ < limit_) update<true>(l, r, U(value), value < 0);
else update<false>(l, r, U(value), value < 0);
} else {
bound_ = 1;
update<false>(l, r, U(value), value < 0);
}
if (minimum_pos_ >= 0 && root_ != candidate) minimum_pos_ = -1;
}
void apply(int l, int r, T value) { add(l, r, value); }
T prod(int l, int r) const {
check(l, r);
if (l == r) return infinity;
if ((l == 0 && r == n_) || (l <= minimum_pos_ && minimum_pos_ < r)) return root_;
if constexpr (sizeof(T) == 8) {
if (U(bound_ - 1) < U(limit_ - 1)) {
#if defined(__AVX2__) && !defined(__AVX512F__) && defined(__x86_64__)
return added(root_, query_vector(l, r));
#else
return added(root_, query<true>(l, r));
#endif
}
if (!bound_) return root_;
}
return added(root_, query<false>(l, r));
}
T min(int l, int r) const { return prod(l, r); }
T all_prod() const { return root_; }
T all_min() const { return root_; }
T get(int p) const { assert(0 <= p && p < n_); return added(root_, restore(0, p, 0)); }
void set(int p, T value) {
assert(0 <= p && p < n_);
T old = get(p);
if (value == old) { if (value == root_) minimum_pos_ = p; return; }
track(value < old ? U(U(old) - U(value)) : U(U(value) - U(old)));
U delta = U(U(value) - U(old)), change;
if constexpr (sizeof(T) == 8) {
change = bound_ < limit_ ? assign<true>(height_ - 1, 0, p, delta, value < old)
: assign<false>(height_ - 1, 0, p, delta, value < old);
} else change = assign<false>(height_ - 1, 0, p, delta, value < old);
root_ = added(root_, change);
if (value == root_) minimum_pos_ = p;
else if (minimum_pos_ == p) minimum_pos_ = -1;
}
std::vector<T> values() const { std::vector<T> result(n_); if (n_) collect(height_ - 1, 0, 0, width_, U(root_), result); return result; }
std::size_t memory_usage() const { return data_.capacity() * sizeof(U); }
void swap(RangeAddRangeMin &other) noexcept {
data_.swap(other.data_), offsets_.swap(other.offsets_), counts_.swap(other.counts_);
std::swap(n_, other.n_), std::swap(minimum_pos_, other.minimum_pos_), std::swap(height_, other.height_), std::swap(width_, other.width_), std::swap(root_, other.root_), std::swap(bound_, other.bound_);
}
friend void swap(RangeAddRangeMin &a, RangeAddRangeMin &b) noexcept { a.swap(b); }
};
#endif
#line 1 "data_structure/range_add_range_min.hpp"
#line 1 "components/aligned_allocator.hpp"
#include <cstddef>
#include <limits>
#include <new>
template<class T, std::size_t Alignment = 64> struct AlignedAllocator {
static_assert(Alignment >= alignof(T) && !(Alignment & (Alignment - 1)));
using value_type = T;
template<class U> struct rebind { using other = AlignedAllocator<U, Alignment>; };
AlignedAllocator() = default;
template<class U> AlignedAllocator(const AlignedAllocator<U, Alignment> &) {}
T *allocate(std::size_t n) {
if (n > std::numeric_limits<std::size_t>::max() / sizeof(T)) throw std::bad_array_new_length();
return static_cast<T *>(::operator new(n * sizeof(T), std::align_val_t(Alignment)));
}
void deallocate(T *p, std::size_t) { ::operator delete(p, std::align_val_t(Alignment)); }
template<class U> bool operator==(const AlignedAllocator<U, Alignment> &) const { return true; }
};
#line 1 "components/range_add_min_node.hpp"
#include <algorithm>
#include <array>
#include <bit>
#line 8 "components/range_add_min_node.hpp"
#include <cstdint>
#line 10 "components/range_add_min_node.hpp"
#include <type_traits>
#include <utility>
#if (defined(__AVX2__) || defined(__AVX512F__)) && defined(__x86_64__)
#include <immintrin.h>
#endif
namespace range_add_min_detail {
template<class T> struct Node {
static_assert(std::is_integral_v<T> && std::is_signed_v<T> && sizeof(T) <= 8);
using U = std::make_unsigned_t<T>;
static constexpr unsigned branch = 8;
static constexpr U umax = std::numeric_limits<U>::max();
static constexpr U sign_bit = U(1) << (sizeof(U) * 8 - 1);
#if defined(__AVX2__) && defined(__x86_64__)
alignas(64) inline static constexpr auto masks_ = [] {
std::array<std::array<U, branch>, branch + 1> masks{};
for (unsigned i = 0; i <= branch; ++i)
for (unsigned j = 0; j < branch; ++j) masks[i][j] = j < i ? umax : 0;
return masks;
}();
alignas(64) inline static constexpr auto slots_ = [] {
std::array<std::array<U, branch>, branch> slots{};
for (unsigned i = 0; i < branch; ++i) slots[i][i] = umax;
return slots;
}();
static __m256i min_signed(__m256i x, __m256i y) { return _mm256_blendv_epi8(x, y, _mm256_cmpgt_epi64(x, y)); }
static __m256i broadcast_min(__m256i value) {
value = min_signed(value, _mm256_permute2x128_si256(value, value, 1));
return min_signed(value, _mm256_permute4x64_epi64(value, 0xb1));
}
static U reduce_min(__m256i value) { return U(_mm_cvtsi128_si64(_mm256_castsi256_si128(broadcast_min(value)))); }
static __m256i broadcast_min32(__m256i value) {
value = _mm256_min_epu32(value, _mm256_permute2x128_si256(value, value, 1));
value = _mm256_min_epu32(value, _mm256_shuffle_epi32(value, 0x4e));
return _mm256_min_epu32(value, _mm256_shuffle_epi32(value, 0xb1));
}
static U reduce_min32(__m256i value) { return U(std::uint32_t(_mm_cvtsi128_si32(_mm256_castsi256_si128(broadcast_min32(value))))); }
template<bool Narrow>
static __m256i minimum_vector(const U* values, unsigned l, unsigned r, U neutral) {
auto identity = _mm256_set1_epi64x(std::bit_cast<T>(neutral));
__m256i result;
for (unsigned i = 0; i < branch; i += 4) {
auto first = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[l].data() + i));
auto last = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[r].data() + i));
auto value = _mm256_load_si256(reinterpret_cast<const __m256i*>(values + i));
if constexpr (!Narrow) value = _mm256_xor_si256(value, _mm256_set1_epi64x(std::bit_cast<T>(sign_bit)));
value = _mm256_blendv_epi8(identity, value, _mm256_xor_si256(first, last));
result = i ? min_signed(result, value) : value;
}
return result;
}
#endif
static T build(U* values, unsigned count) {
if (!count) return std::numeric_limits<T>::max();
#if defined(__AVX512F__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto value = _mm512_loadu_si512(values);
unsigned valid = (1u << count) - 1;
T minimum = T(_mm512_mask_reduce_min_epi64(valid, value));
value = _mm512_mask_sub_epi64(value, valid, value, _mm512_set1_epi64(minimum));
_mm512_storeu_si512(values, value);
return minimum;
}
#endif
#if defined(__AVX2__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto first = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[count].data()));
auto last = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[count].data() + 4));
auto x = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values));
auto y = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values + 4));
auto identity = _mm256_set1_epi64x(std::numeric_limits<T>::max());
auto a = _mm256_blendv_epi8(identity, x, first), b = _mm256_blendv_epi8(identity, y, last);
auto minimum = broadcast_min(min_signed(a, b));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values), _mm256_sub_epi64(x, _mm256_and_si256(first, minimum)));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values + 4), _mm256_sub_epi64(y, _mm256_and_si256(last, minimum)));
return std::bit_cast<T>(U(_mm_cvtsi128_si64(_mm256_castsi256_si128(minimum))));
}
if constexpr (sizeof(T) == 4) {
auto valid = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[count].data()));
auto value = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values));
auto sign = _mm256_set1_epi32(std::bit_cast<T>(sign_bit));
auto key = _mm256_xor_si256(value, sign);
key = _mm256_or_si256(key, _mm256_andnot_si256(valid, _mm256_set1_epi32(-1)));
auto minimum = _mm256_xor_si256(broadcast_min32(key), sign);
value = _mm256_sub_epi32(value, _mm256_and_si256(valid, minimum));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values), value);
return std::bit_cast<T>(U(std::uint32_t(_mm_cvtsi128_si32(_mm256_castsi256_si128(minimum)))));
}
#endif
T minimum = std::bit_cast<T>(values[0]);
for (unsigned i = 1; i < count; ++i) minimum = std::min(minimum, std::bit_cast<T>(values[i]));
for (unsigned i = 0; i < count; ++i) values[i] = U(values[i] - U(minimum));
return minimum;
}
template<bool Narrow>
static U minimum(const U* values, unsigned l, unsigned r) {
#if defined(__AVX512F__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
unsigned mask = ((1u << r) - 1) ^ ((1u << l) - 1);
auto value = _mm512_loadu_si512(values);
if constexpr (Narrow) return U(_mm512_mask_reduce_min_epi64(mask, value));
else return U(_mm512_mask_reduce_min_epu64(mask, value));
}
#endif
#if defined(__AVX2__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
U result = reduce_min(minimum_vector<Narrow>(values, l, r, U(std::numeric_limits<T>::max())));
if constexpr (Narrow) return result;
else return result ^ sign_bit;
}
if constexpr (sizeof(T) == 4) {
auto first = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[l].data()));
auto last = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[r].data()));
auto value = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values));
auto excluded = _mm256_xor_si256(_mm256_xor_si256(first, last), _mm256_set1_epi32(-1));
return reduce_min32(_mm256_or_si256(value, excluded));
}
#endif
U result = umax;
for (unsigned i = l; i < r; ++i) result = std::min(result, values[i]);
return result;
}
template<bool Narrow>
static U normalize(U *values, unsigned count, bool negative, unsigned first, unsigned last, U delta, unsigned x = 0, U dx = 0, unsigned y = 0, U dy = 0) {
#if defined(__AVX512F__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto old = _mm512_loadu_si512(values);
unsigned mask = ((1u << last) - 1) ^ ((1u << first) - 1), valid = (1u << count) - 1;
auto next = _mm512_mask_add_epi64(old, mask, old, _mm512_set1_epi64(std::bit_cast<T>(delta)));
next = _mm512_mask_add_epi64(next, 1u << x, next, _mm512_set1_epi64(std::bit_cast<T>(dx)));
next = _mm512_mask_add_epi64(next, 1u << y, next, _mm512_set1_epi64(std::bit_cast<T>(dy)));
U change;
if constexpr (Narrow) {
change = U(_mm512_reduce_min_epi64(next));
next = _mm512_sub_epi64(next, _mm512_set1_epi64(std::bit_cast<T>(change)));
} else {
unsigned wrap = negative ? unsigned(_mm512_cmp_epu64_mask(next, old, _MM_CMPINT_GT)) & valid : 0;
change = U(_mm512_mask_reduce_min_epu64(wrap ? wrap : valid, next));
next = _mm512_mask_sub_epi64(next, valid, next, _mm512_set1_epi64(std::bit_cast<T>(change)));
}
_mm512_storeu_si512(values, next);
return change;
}
#endif
#if defined(__AVX2__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto identity = _mm256_set1_epi64x(std::numeric_limits<T>::max());
__m256i next[2], result, wrapped = identity;
auto underflow = _mm256_setzero_si256();
for (unsigned i = 0; i < branch; i += 4) {
auto a = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[first].data() + i));
auto b = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[last].data() + i));
auto old = _mm256_load_si256(reinterpret_cast<const __m256i*>(values + i));
auto value = _mm256_add_epi64(old, _mm256_and_si256(_mm256_xor_si256(a, b), _mm256_set1_epi64x(std::bit_cast<T>(delta))));
value = _mm256_add_epi64(value, _mm256_and_si256(_mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[x].data() + i)), _mm256_set1_epi64x(std::bit_cast<T>(dx))));
value = _mm256_add_epi64(value, _mm256_and_si256(_mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[y].data() + i)), _mm256_set1_epi64x(std::bit_cast<T>(dy))));
next[i / 4] = value;
if constexpr (!Narrow) {
auto biased = _mm256_xor_si256(value, _mm256_set1_epi64x(std::bit_cast<T>(sign_bit)));
result = i ? min_signed(result, biased) : biased;
if (negative) {
auto wrap = _mm256_cmpgt_epi64(biased, _mm256_xor_si256(old, _mm256_set1_epi64x(std::bit_cast<T>(sign_bit))));
underflow = _mm256_or_si256(underflow, wrap);
wrapped = min_signed(wrapped, _mm256_blendv_epi8(identity, biased, wrap));
}
}
}
__m256i shift;
U change;
if constexpr (Narrow) {
shift = broadcast_min(min_signed(next[0], next[1]));
change = U(_mm_cvtsi128_si64(_mm256_castsi256_si128(shift)));
} else {
change = reduce_min(negative && _mm256_movemask_epi8(underflow) ? wrapped : result) ^ sign_bit;
shift = _mm256_set1_epi64x(std::bit_cast<T>(change));
}
for (unsigned i = 0; i < branch; i += 4) {
auto delta = shift;
if constexpr (!Narrow) delta = _mm256_and_si256(delta, _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[count].data() + i)));
_mm256_store_si256(reinterpret_cast<__m256i*>(values + i), _mm256_sub_epi64(next[i / 4], delta));
}
return change;
}
if constexpr (sizeof(T) == 4) {
auto first_mask = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[first].data()));
auto last_mask = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[last].data()));
auto old = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values));
auto next = _mm256_add_epi32(old, _mm256_and_si256(_mm256_xor_si256(first_mask, last_mask), _mm256_set1_epi32(std::bit_cast<T>(delta))));
next = _mm256_add_epi32(next, _mm256_and_si256(_mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[x].data())), _mm256_set1_epi32(std::bit_cast<T>(dx))));
next = _mm256_add_epi32(next, _mm256_and_si256(_mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[y].data())), _mm256_set1_epi32(std::bit_cast<T>(dy))));
auto candidates = next;
if (negative) {
auto sign = _mm256_set1_epi32(std::bit_cast<T>(sign_bit));
auto wrapped = _mm256_cmpgt_epi32(_mm256_xor_si256(next, sign), _mm256_xor_si256(old, sign));
if (_mm256_movemask_epi8(wrapped)) candidates = _mm256_or_si256(next, _mm256_andnot_si256(wrapped, _mm256_set1_epi32(-1)));
}
U change = reduce_min32(candidates);
auto valid = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[count].data()));
next = _mm256_sub_epi32(next, _mm256_and_si256(valid, _mm256_set1_epi32(std::bit_cast<T>(change))));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values), next);
return change;
}
#endif
U wrapped = umax, result = umax;
bool underflow = false;
for (unsigned i = 0; i < count; ++i) {
U old = values[i], change = first <= i && i < last ? delta : 0;
if (i == x) change += dx;
if (i == y) change += dy;
U next = U(old + change);
values[i] = next;
if (negative && next > old) { wrapped = std::min(wrapped, next); underflow = true; }
result = std::min(result, next);
}
if (underflow) result = wrapped;
for (unsigned i = 0; i < count; ++i) values[i] -= result;
return result;
}
template<bool Narrow>
static std::pair<U, U> normalize_boundaries(U* left, U* right, unsigned right_count, bool negative, unsigned first, unsigned last, U delta, U left_change, U right_change) {
#if defined(__AVX2__) && !defined(__AVX512F__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8 && Narrow) {
__m256i x[2], y[2];
auto common = _mm256_set1_epi64x(std::bit_cast<T>(delta));
auto dx = _mm256_set1_epi64x(std::bit_cast<T>(left_change));
auto dy = _mm256_set1_epi64x(std::bit_cast<T>(right_change));
for (unsigned i = 0; i < branch; i += 4) {
auto prefix = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[first].data() + i));
auto suffix = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[last + 1].data() + i));
auto lc = _mm256_andnot_si256(prefix, common);
auto rc = _mm256_and_si256(suffix, common);
lc = _mm256_blendv_epi8(lc, dx, _mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[first].data() + i)));
rc = _mm256_blendv_epi8(rc, dy, _mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[last].data() + i)));
x[i / 4] = _mm256_add_epi64(_mm256_load_si256(reinterpret_cast<const __m256i*>(left + i)), lc);
y[i / 4] = _mm256_add_epi64(_mm256_load_si256(reinterpret_cast<const __m256i*>(right + i)), rc);
}
auto a = min_signed(x[0], x[1]), b = min_signed(y[0], y[1]);
auto minimum = min_signed(_mm256_unpacklo_epi64(a, b), _mm256_unpackhi_epi64(a, b));
minimum = min_signed(minimum, _mm256_permute2x128_si256(minimum, minimum, 1));
auto lm = _mm256_permute4x64_epi64(minimum, 0x00), rm = _mm256_permute4x64_epi64(minimum, 0x55);
_mm256_store_si256(reinterpret_cast<__m256i*>(left), _mm256_sub_epi64(x[0], lm));
_mm256_store_si256(reinterpret_cast<__m256i*>(left + 4), _mm256_sub_epi64(x[1], lm));
_mm256_store_si256(reinterpret_cast<__m256i*>(right), _mm256_sub_epi64(y[0], rm));
_mm256_store_si256(reinterpret_cast<__m256i*>(right + 4), _mm256_sub_epi64(y[1], rm));
return {U(_mm_cvtsi128_si64(_mm256_castsi256_si128(minimum))), U(_mm_extract_epi64(_mm256_castsi256_si128(minimum), 1))};
}
#endif
#if defined(__AVX2__) && defined(__x86_64__)
if constexpr (sizeof(T) == 4) {
auto common = _mm256_set1_epi32(std::bit_cast<T>(delta));
auto prefix = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[first].data()));
auto suffix = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[last + 1].data()));
auto lc = _mm256_andnot_si256(prefix, common);
auto rc = _mm256_and_si256(suffix, common);
lc = _mm256_blendv_epi8(lc, _mm256_set1_epi32(std::bit_cast<T>(left_change)), _mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[first].data())));
rc = _mm256_blendv_epi8(rc, _mm256_set1_epi32(std::bit_cast<T>(right_change)), _mm256_load_si256(reinterpret_cast<const __m256i*>(slots_[last].data())));
auto old_left = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(left));
auto old_right = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(right));
auto x = _mm256_add_epi32(old_left, lc), y = _mm256_add_epi32(old_right, rc);
auto a = x, b = y;
if (negative) {
auto sign = _mm256_set1_epi32(std::bit_cast<T>(sign_bit));
auto lx = _mm256_cmpgt_epi32(_mm256_xor_si256(x, sign), _mm256_xor_si256(old_left, sign));
auto ry = _mm256_cmpgt_epi32(_mm256_xor_si256(y, sign), _mm256_xor_si256(old_right, sign));
if (_mm256_movemask_epi8(lx)) a = _mm256_or_si256(x, _mm256_andnot_si256(lx, _mm256_set1_epi32(-1)));
if (_mm256_movemask_epi8(ry)) b = _mm256_or_si256(y, _mm256_andnot_si256(ry, _mm256_set1_epi32(-1)));
}
auto minimum = _mm256_min_epu32(_mm256_unpacklo_epi32(a, b), _mm256_unpackhi_epi32(a, b));
minimum = _mm256_min_epu32(minimum, _mm256_shuffle_epi32(minimum, 0x4e));
minimum = _mm256_min_epu32(minimum, _mm256_permute2x128_si256(minimum, minimum, 1));
auto lm = _mm256_shuffle_epi32(minimum, 0x00), rm = _mm256_shuffle_epi32(minimum, 0x55);
x = _mm256_sub_epi32(x, lm);
y = _mm256_sub_epi32(y, _mm256_and_si256(rm, _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[right_count].data()))));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(left), x);
_mm256_storeu_si256(reinterpret_cast<__m256i*>(right), y);
auto low = _mm256_castsi256_si128(minimum);
return {U(std::uint32_t(_mm_cvtsi128_si32(low))), U(std::uint32_t(_mm_extract_epi32(low, 1)))};
}
#endif
U a = first + 1 == branch ? change_one<Narrow>(left, branch, first, left_change, negative)
: normalize<Narrow>(left, branch, negative, first + 1, branch, delta, first, left_change);
U b = !last ? change_one<Narrow>(right, right_count, 0, right_change, negative)
: normalize<Narrow>(right, right_count, negative, 0, last, delta, last, right_change);
return {a, b};
}
template<bool Narrow>
static U full_minimum(const U* values) {
#if defined(__AVX512F__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto value = _mm512_loadu_si512(values);
if constexpr (Narrow) return U(_mm512_reduce_min_epi64(value));
else return U(_mm512_reduce_min_epu64(value));
}
#endif
#if defined(__AVX2__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto result = _mm256_load_si256(reinterpret_cast<const __m256i*>(values));
if constexpr (!Narrow) result = _mm256_xor_si256(result, _mm256_set1_epi64x(std::bit_cast<T>(sign_bit)));
for (unsigned i = 4; i < branch; i += 4) {
auto value = _mm256_load_si256(reinterpret_cast<const __m256i*>(values + i));
if constexpr (!Narrow) value = _mm256_xor_si256(value, _mm256_set1_epi64x(std::bit_cast<T>(sign_bit)));
result = min_signed(result, value);
}
if constexpr (Narrow) return reduce_min(result);
else return reduce_min(result) ^ sign_bit;
}
if constexpr (sizeof(T) == 4) return reduce_min32(_mm256_loadu_si256(reinterpret_cast<const __m256i*>(values)));
#endif
U result = umax;
for (unsigned i = 0; i < branch; ++i) result = std::min(result, values[i]);
return result;
}
static void subtract(U* values, unsigned count, U change) {
#if defined(__AVX512F__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto value = _mm512_loadu_si512(values);
value = _mm512_mask_sub_epi64(value, (1u << count) - 1, value, _mm512_set1_epi64(std::bit_cast<T>(change)));
_mm512_storeu_si512(values, value);
return;
}
#endif
#if defined(__AVX2__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto delta = _mm256_set1_epi64x(std::bit_cast<T>(change));
for (unsigned i = 0; i < branch; i += 4) {
auto valid = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[count].data() + i));
auto old = _mm256_load_si256(reinterpret_cast<const __m256i*>(values + i));
_mm256_store_si256(reinterpret_cast<__m256i*>(values + i), _mm256_sub_epi64(old, _mm256_and_si256(valid, delta)));
}
return;
}
if constexpr (sizeof(T) == 4) {
auto valid = _mm256_load_si256(reinterpret_cast<const __m256i*>(masks_[count].data()));
auto value = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values));
value = _mm256_sub_epi32(value, _mm256_and_si256(valid, _mm256_set1_epi32(std::bit_cast<T>(change))));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(values), value);
return;
}
#endif
for (unsigned i = 0; i < count; ++i) values[i] -= change;
}
static void materialize(const U* values, T* result, unsigned count, U base) {
if (count == branch) {
#if defined(__AVX512F__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto value = _mm512_loadu_si512(values);
value = _mm512_add_epi64(value, _mm512_set1_epi64(std::bit_cast<T>(base)));
_mm512_storeu_si512(result, value);
return;
}
#endif
#if defined(__AVX2__) && defined(__x86_64__)
if constexpr (sizeof(T) == 8) {
auto delta = _mm256_set1_epi64x(std::bit_cast<T>(base));
for (unsigned i = 0; i < branch; i += 4) {
auto value = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values + i));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(result + i), _mm256_add_epi64(value, delta));
}
return;
}
if constexpr (sizeof(T) == 4) {
auto value = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(values));
value = _mm256_add_epi32(value, _mm256_set1_epi32(std::bit_cast<T>(base)));
_mm256_storeu_si256(reinterpret_cast<__m256i*>(result), value);
return;
}
if constexpr (sizeof(T) == 2) {
auto value = _mm_loadu_si128(reinterpret_cast<const __m128i*>(values));
value = _mm_add_epi16(value, _mm_set1_epi16(std::bit_cast<T>(base)));
_mm_storeu_si128(reinterpret_cast<__m128i*>(result), value);
return;
}
if constexpr (sizeof(T) == 1) {
auto value = _mm_loadl_epi64(reinterpret_cast<const __m128i*>(values));
value = _mm_add_epi8(value, _mm_set1_epi8(std::bit_cast<T>(base)));
_mm_storel_epi64(reinterpret_cast<__m128i*>(result), value);
return;
}
#endif
}
for (unsigned i = 0; i < count; ++i) result[i] = std::bit_cast<T>(U(values[i] + base));
}
template<bool Narrow>
static U change_one(U *values, unsigned count, unsigned index, U delta, bool negative) {
if (!delta) return 0;
U old = values[index], next = U(old + delta);
values[index] = next;
if ((Narrow && sizeof(T) == 8) ? std::bit_cast<T>(next) < 0 : negative && next > old) {
subtract(values, count, next);
return next;
}
if (((Narrow && sizeof(T) == 8) || !negative) && !old) {
U result = full_minimum<Narrow>(values);
if (!result) return 0;
subtract(values, count, result);
return result;
}
return 0;
}
};
}
#line 9 "data_structure/range_add_range_min.hpp"
#include <cassert>
#line 13 "data_structure/range_add_range_min.hpp"
#include <stdexcept>
#line 16 "data_structure/range_add_range_min.hpp"
#include <vector>
template<class T = std::int64_t> class RangeAddRangeMin {
static_assert(std::is_integral_v<T> && std::is_signed_v<T> && sizeof(T) <= 8);
using U = std::make_unsigned_t<T>;
using Node = range_add_min_detail::Node<T>;
static constexpr unsigned branch = 8, bits = 3;
static constexpr T infinity = std::numeric_limits<T>::max();
static constexpr U umax = std::numeric_limits<U>::max();
static constexpr U limit_ = U(infinity) / 3;
std::vector<U, AlignedAllocator<U>> data_;
std::array<std::size_t, (sizeof(int) * 8 + bits - 1) / bits + 1> offsets_{}, counts_{};
int n_ = 0, minimum_pos_ = -1;
unsigned height_ = 0;
std::size_t width_ = 1;
T root_ = infinity;
U bound_ = 0;
static T added(T value, U delta) { return std::bit_cast<T>(U(U(value) + delta)); }
unsigned block_count(unsigned level, std::size_t index) const { return unsigned(std::min<std::size_t>(branch, counts_[level] - index * branch)); }
template<bool Narrow>
void propagate(unsigned level, std::size_t index, U change, bool negative) {
for (; level < height_; ++level, index >>= bits) {
if (!change) return;
std::size_t block = index >> bits;
change = Node::template change_one<Narrow>(data_.data() + offsets_[level] + block * branch, block_count(level, block), index & (branch - 1), change, negative);
}
root_ = added(root_, change);
}
template<bool Narrow>
void update(std::size_t l, std::size_t r, U delta, bool negative) {
--r;
std::size_t a = l >> bits, b = r >> bits;
unsigned first = unsigned(l & (branch - 1)), last = unsigned(r & (branch - 1));
if (a == b) {
U change = first == last ? Node::template change_one<Narrow>(data_.data() + a * branch, block_count(0, a), first, delta, negative)
: Node::template normalize<Narrow>(data_.data() + a * branch, block_count(0, a), negative, first, last + 1, delta);
propagate<Narrow>(1, a, change, negative);
return;
}
auto ends = Node::template normalize_boundaries<Narrow>(data_.data() + a * branch, data_.data() + b * branch, block_count(0, b), negative, first, last, delta, delta, delta);
U left = ends.first, right = ends.second;
for (unsigned level = 1;; ++level) {
l >>= bits;
r >>= bits;
first = unsigned(l & (branch - 1));
last = unsigned(r & (branch - 1));
a = l >> bits;
b = r >> bits;
U *values = data_.data() + offsets_[level];
if (a == b) {
U change;
if (first + 1 == last) {
change = Node::template change_one<Narrow>(values + a * branch, block_count(level, a), first, left, negative);
change += Node::template change_one<Narrow>(values + a * branch, block_count(level, a), last, right, negative);
} else change = Node::template normalize<Narrow>(values + a * branch, block_count(level, a), negative, first + 1, last, delta, first, left, last, right);
propagate<Narrow>(level + 1, a, change, negative);
return;
}
if (first + 1 < branch && last) {
auto ends = Node::template normalize_boundaries<Narrow>(values + a * branch, values + b * branch, block_count(level, b), negative, first, last, delta, left, right);
left = ends.first, right = ends.second;
} else {
left = first + 1 == branch ? Node::template change_one<Narrow>(values + a * branch, branch, first, left, negative)
: Node::template normalize<Narrow>(values + a * branch, branch, negative, first + 1, branch, delta, first, left);
right = !last ? Node::template change_one<Narrow>(values + b * branch, block_count(level, b), 0, right, negative)
: Node::template normalize<Narrow>(values + b * branch, block_count(level, b), negative, 0, last, delta, last, right);
}
}
}
U restore(unsigned level, std::size_t index, U result) const {
for (; level < height_; ++level, index >>= bits) result += data_[offsets_[level] + index];
return result;
}
template<bool Narrow>
U query(std::size_t l, std::size_t r) const {
if constexpr (sizeof(T) < 8) if (!bound_) return 0;
--r;
std::size_t a = l >> bits, b = r >> bits;
if (a == b) {
if (l == r) return restore(0, l, 0);
return restore(1, a, Node::template minimum<Narrow>(data_.data() + a * branch, l & (branch - 1), (r & (branch - 1)) + 1));
}
U left = Node::template minimum<Narrow>(data_.data() + a * branch, l & (branch - 1), branch);
U right = Node::template minimum<Narrow>(data_.data() + b * branch, 0, (r & (branch - 1)) + 1);
for (unsigned level = 1;; ++level) {
l >>= bits;
r >>= bits;
left += data_[offsets_[level] + l];
right += data_[offsets_[level] + r];
unsigned first = unsigned(l & (branch - 1)), last = unsigned(r & (branch - 1));
a = l >> bits;
b = r >> bits;
const U *values = data_.data() + offsets_[level];
if (a == b) {
U result = std::min(left, right);
if (first + 1 < last) result = std::min(result, Node::template minimum<Narrow>(values + a * branch, first + 1, last));
return restore(level + 1, a, result);
}
if (first + 1 < branch) left = std::min(left, Node::template minimum<Narrow>(values + a * branch, first + 1, branch));
if (last) right = std::min(right, Node::template minimum<Narrow>(values + b * branch, 0, last));
}
}
#if defined(__AVX2__) && !defined(__AVX512F__) && defined(__x86_64__)
static __m256i query_block(const U* values, unsigned first, unsigned last) {
return Node::template minimum_vector<true>(values, first, last, 2 * limit_);
}
U query_vector(std::size_t l, std::size_t r) const {
--r;
std::size_t a = l >> bits, b = r >> bits;
if (a == b) {
if (l == r) return restore(0, l, 0);
auto value = query_block(data_.data() + a * branch, l & (branch - 1), (r & (branch - 1)) + 1);
U carry = restore(1, a, 0);
return Node::reduce_min(value) + carry;
}
auto left = query_block(data_.data() + a * branch, l & (branch - 1), branch);
auto right = query_block(data_.data() + b * branch, 0, (r & (branch - 1)) + 1);
for (unsigned level = 1;; ++level) {
l >>= bits;
r >>= bits;
left = _mm256_add_epi64(left, _mm256_set1_epi64x(std::int64_t(data_[offsets_[level] + l])));
right = _mm256_add_epi64(right, _mm256_set1_epi64x(std::int64_t(data_[offsets_[level] + r])));
unsigned first = unsigned(l & (branch - 1)), last = unsigned(r & (branch - 1));
a = l >> bits;
b = r >> bits;
const U* values = data_.data() + offsets_[level];
if (a == b) {
auto result = Node::min_signed(left, right);
if (first + 1 < last) result = Node::min_signed(result, query_block(values + a * branch, first + 1, last));
U carry = restore(level + 1, a, 0);
return Node::reduce_min(result) + carry;
}
if (first + 1 < branch) left = Node::min_signed(left, query_block(values + a * branch, first + 1, branch));
if (last) right = Node::min_signed(right, query_block(values + b * branch, 0, last));
}
}
#endif
template<bool Narrow>
U assign(unsigned level, std::size_t index, std::size_t pos, U delta, bool negative) {
unsigned child = unsigned((pos >> (bits * level)) & (branch - 1));
U change = level ? assign<Narrow>(level - 1, index * branch + child, pos, delta, negative) : delta;
unsigned count = unsigned(std::min<std::size_t>(branch, counts_[level] - index * branch));
return Node::template change_one<Narrow>(data_.data() + offsets_[level] + index * branch, count, child, change, negative);
}
void collect(unsigned level, std::size_t index, std::size_t start, std::size_t width, U base, std::vector<T> &result) const {
const U *values = data_.data() + offsets_[level] + index * branch;
if (!level) {
unsigned count = unsigned(std::min<std::size_t>(branch, std::size_t(n_) - start));
Node::materialize(values, result.data() + start, count, base);
return;
}
std::size_t part = width / branch;
for (unsigned i = 0; i < branch && start + i * part < std::size_t(n_); ++i)
collect(level - 1, index * branch + i, start + i * part, part, U(base + values[i]), result);
}
void padding(U value) {
for (unsigned level = 0; level < height_; ++level) {
std::size_t count = counts_[level], remainder = count & (branch - 1);
if (remainder) {
U* first = data_.data() + offsets_[level] + count;
std::fill(first, first + branch - remainder, value);
}
}
}
void track(U amount) {
if constexpr (sizeof(T) == 8) {
bool narrow = bound_ < limit_;
bound_ = narrow && amount < limit_ - bound_ ? U(bound_ + amount) : umax;
if (narrow && bound_ == umax) padding(umax);
} else bound_ = 1;
}
void allocate(int n, U value) {
n_ = n;
if (!n) return;
std::size_t total = 0, count = n;
for (unsigned level = 0;; ++level) {
std::size_t groups = (count + branch - 1) / branch;
offsets_[level] = total;
counts_[level] = count;
total += groups * branch;
if (width_ > std::numeric_limits<std::size_t>::max() / branch) throw std::length_error("RangeAddRangeMin size");
width_ *= branch;
if (groups == 1) { height_ = level + 1; break; }
count = groups;
}
data_.resize(total, value);
}
void check([[maybe_unused]] int l, [[maybe_unused]] int r) const { assert(0 <= l && l <= r && r <= n_); }
public:
using value_type = T;
RangeAddRangeMin() = default;
explicit RangeAddRangeMin(int n, T value = 0) {
assert(n >= 0);
allocate(n, 0);
if (n) { root_ = value; minimum_pos_ = n / 2; padding(sizeof(T) == 8 ? 2 * limit_ : umax); }
}
explicit RangeAddRangeMin(const std::vector<T> &values) { build(values); }
RangeAddRangeMin(const RangeAddRangeMin &) = default;
RangeAddRangeMin(RangeAddRangeMin &&other) noexcept { swap(other); }
RangeAddRangeMin &operator=(RangeAddRangeMin other) noexcept { swap(other); return *this; }
void build(const std::vector<T> &values) {
assert(values.size() <= std::size_t(std::numeric_limits<int>::max()));
auto extremes = std::minmax_element(values.begin(), values.end());
if (!values.empty() && *extremes.first == *extremes.second) {
RangeAddRangeMin next(int(values.size()), *extremes.first);
swap(next);
return;
}
RangeAddRangeMin next;
next.allocate(int(values.size()), umax);
if (!values.empty()) {
std::copy(values.begin(), values.end(), next.data_.begin());
for (unsigned level = 0; level < next.height_; ++level) {
std::size_t groups = (next.counts_[level] + branch - 1) / branch;
for (std::size_t group = 0; group < groups; ++group) {
T minimum = Node::build(next.data_.data() + next.offsets_[level] + group * branch, next.block_count(level, group));
if (level + 1 == next.height_) next.root_ = minimum;
else next.data_[next.offsets_[level + 1] + group] = U(minimum);
}
}
next.minimum_pos_ = values[values.size() / 2] == next.root_ ? int(values.size() / 2) : int(extremes.first - values.begin());
next.bound_ = U(U(*extremes.second) - U(next.root_));
if constexpr (sizeof(T) == 8) if (next.bound_ < limit_) next.padding(2 * limit_);
}
swap(next);
}
int size() const { return n_; }
bool empty() const { return !n_; }
void add(int l, int r, T value) {
check(l, r);
if (l == r || !value) return;
if (l == 0 && r == n_) { root_ = added(root_, U(value)); return; }
T candidate = root_;
if (l <= minimum_pos_ && minimum_pos_ < r) candidate = added(root_, U(value));
if constexpr (sizeof(T) == 8) {
track(value < 0 ? U(0) - U(value) : U(value));
if (bound_ < limit_) update<true>(l, r, U(value), value < 0);
else update<false>(l, r, U(value), value < 0);
} else {
bound_ = 1;
update<false>(l, r, U(value), value < 0);
}
if (minimum_pos_ >= 0 && root_ != candidate) minimum_pos_ = -1;
}
void apply(int l, int r, T value) { add(l, r, value); }
T prod(int l, int r) const {
check(l, r);
if (l == r) return infinity;
if ((l == 0 && r == n_) || (l <= minimum_pos_ && minimum_pos_ < r)) return root_;
if constexpr (sizeof(T) == 8) {
if (U(bound_ - 1) < U(limit_ - 1)) {
#if defined(__AVX2__) && !defined(__AVX512F__) && defined(__x86_64__)
return added(root_, query_vector(l, r));
#else
return added(root_, query<true>(l, r));
#endif
}
if (!bound_) return root_;
}
return added(root_, query<false>(l, r));
}
T min(int l, int r) const { return prod(l, r); }
T all_prod() const { return root_; }
T all_min() const { return root_; }
T get(int p) const { assert(0 <= p && p < n_); return added(root_, restore(0, p, 0)); }
void set(int p, T value) {
assert(0 <= p && p < n_);
T old = get(p);
if (value == old) { if (value == root_) minimum_pos_ = p; return; }
track(value < old ? U(U(old) - U(value)) : U(U(value) - U(old)));
U delta = U(U(value) - U(old)), change;
if constexpr (sizeof(T) == 8) {
change = bound_ < limit_ ? assign<true>(height_ - 1, 0, p, delta, value < old)
: assign<false>(height_ - 1, 0, p, delta, value < old);
} else change = assign<false>(height_ - 1, 0, p, delta, value < old);
root_ = added(root_, change);
if (value == root_) minimum_pos_ = p;
else if (minimum_pos_ == p) minimum_pos_ = -1;
}
std::vector<T> values() const { std::vector<T> result(n_); if (n_) collect(height_ - 1, 0, 0, width_, U(root_), result); return result; }
std::size_t memory_usage() const { return data_.capacity() * sizeof(U); }
void swap(RangeAddRangeMin &other) noexcept {
data_.swap(other.data_), offsets_.swap(other.offsets_), counts_.swap(other.counts_);
std::swap(n_, other.n_), std::swap(minimum_pos_, other.minimum_pos_), std::swap(height_, other.height_), std::swap(width_, other.width_), std::swap(root_, other.root_), std::swap(bound_, other.bound_);
}
friend void swap(RangeAddRangeMin &a, RangeAddRangeMin &b) noexcept { a.swap(b); }
};