#line 1 "verify/ds/rollback_counterparts.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 1 "ds/bst/rollback_ordered_multiset.hpp"
#include <cassert>
#include <functional>
#include <initializer_list>
#include <optional>
#include <utility>
#include <vector>
#line 1 "ds/bst/ordered_multiset.hpp"
#line 7 "ds/bst/ordered_multiset.hpp"
#include <memory>
#line 10 "ds/bst/ordered_multiset.hpp"
namespace m1une {
namespace ds {
template <typename T, typename Compare = std::less<T>>
struct OrderedMultiset {
private:
struct Node {
T key;
int count;
int size;
int distinct_size;
Node* l;
Node* r;
Node(T value, int multiplicity)
: key(std::move(value)),
count(multiplicity),
size(multiplicity),
distinct_size(1),
l(nullptr),
r(nullptr) {}
};
static constexpr int pool_block_size = 1 << 14;
struct Pool {
std::vector<std::vector<Node>> blocks;
std::vector<Node*> free_nodes;
template <class... Args>
Node* emplace(Args&&... args) {
if (!free_nodes.empty()) {
Node* result = free_nodes.back();
free_nodes.pop_back();
std::destroy_at(result);
std::construct_at(result, std::forward<Args>(args)...);
return result;
}
if (blocks.empty() || int(blocks.back().size()) == pool_block_size) {
blocks.emplace_back();
blocks.back().reserve(pool_block_size);
}
blocks.back().emplace_back(std::forward<Args>(args)...);
return &blocks.back().back();
}
void recycle(Node* node) {
free_nodes.push_back(node);
}
};
inline static Pool pool;
Node* root;
Compare comp;
static int subtree_size(const Node* t) {
return t == nullptr ? 0 : t->size;
}
static int subtree_distinct_size(const Node* t) {
return t == nullptr ? 0 : t->distinct_size;
}
bool equal(const T& a, const T& b) const {
return !comp(a, b) && !comp(b, a);
}
Node* new_node(T key, int multiplicity) {
return pool.emplace(std::move(key), multiplicity);
}
static void update(Node* t) {
t->size = t->count + subtree_size(t->l) + subtree_size(t->r);
t->distinct_size = 1 + subtree_distinct_size(t->l) + subtree_distinct_size(t->r);
}
static Node* rotate_right(Node* t) {
Node* s = t->l;
t->l = s->r;
s->r = t;
update(t);
update(s);
return s;
}
static Node* rotate_left(Node* t) {
Node* s = t->r;
t->r = s->l;
s->l = t;
update(t);
update(s);
return s;
}
static Node* balance(Node* t) {
if (t == nullptr) return nullptr;
const int left_size = subtree_distinct_size(t->l);
const int right_size = subtree_distinct_size(t->r);
if (left_size + right_size > 1 && left_size > 3LL * right_size) {
if (subtree_distinct_size(t->l->r) >= 2LL * subtree_distinct_size(t->l->l)) {
t->l = rotate_left(t->l);
}
return rotate_right(t);
}
if (left_size + right_size > 1 && right_size > 3LL * left_size) {
if (subtree_distinct_size(t->r->l) >= 2LL * subtree_distinct_size(t->r->r)) {
t->r = rotate_right(t->r);
}
return rotate_left(t);
}
update(t);
return t;
}
static Node* join_with_root(Node* l, Node* middle, Node* r) {
const int left_size = subtree_distinct_size(l);
const int right_size = subtree_distinct_size(r);
if (left_size > 3LL * (right_size + 1)) {
l->r = join_with_root(l->r, middle, r);
return balance(l);
}
if (right_size > 3LL * (left_size + 1)) {
r->l = join_with_root(l, middle, r->l);
return balance(r);
}
middle->l = l;
middle->r = r;
return balance(middle);
}
static Node* detach_max(Node* t, Node*& maximum) {
if (t->r == nullptr) {
maximum = t;
return t->l;
}
t->r = detach_max(t->r, maximum);
return balance(t);
}
static Node* merge_nodes(Node* l, Node* r) {
if (l == nullptr || r == nullptr) return l == nullptr ? r : l;
Node* middle;
l = detach_max(l, middle);
return join_with_root(l, middle, r);
}
std::pair<Node*, Node*> split_nodes(Node* t, const T& key) {
if (t == nullptr) return {nullptr, nullptr};
Node* left = t->l;
Node* right = t->r;
t->l = nullptr;
t->r = nullptr;
if (comp(t->key, key)) {
auto [l, r] = split_nodes(right, key);
return {join_with_root(left, t, l), r};
}
auto [l, r] = split_nodes(left, key);
return {l, join_with_root(r, t, right)};
}
Node* insert_impl(Node* t, T& key, int multiplicity, bool& new_key) {
if (t == nullptr) {
new_key = true;
return new_node(std::move(key), multiplicity);
}
if (comp(key, t->key)) {
t->l = insert_impl(t->l, key, multiplicity, new_key);
} else if (comp(t->key, key)) {
t->r = insert_impl(t->r, key, multiplicity, new_key);
} else {
t->count += multiplicity;
t->size += multiplicity;
new_key = false;
return t;
}
if (!new_key) {
t->size += multiplicity;
return t;
}
return balance(t);
}
Node* erase_impl(Node* t, const T& key, bool erase_all,
int& erased, bool& removed_key) {
if (t == nullptr) return nullptr;
if (comp(key, t->key)) {
t->l = erase_impl(t->l, key, erase_all, erased, removed_key);
} else if (comp(t->key, key)) {
t->r = erase_impl(t->r, key, erase_all, erased, removed_key);
} else if (!erase_all && t->count > 1) {
--t->count;
--t->size;
erased = 1;
removed_key = false;
return t;
} else {
erased = t->count;
removed_key = true;
Node* l = t->l;
Node* r = t->r;
pool.recycle(t);
return merge_nodes(l, r);
}
if (erased == 0) return t;
if (!removed_key) {
t->size -= erased;
return t;
}
return balance(t);
}
static const T* kth_impl(const Node* t, int k) {
while (t != nullptr) {
const int left_size = subtree_size(t->l);
if (k < left_size) {
t = t->l;
} else if (k < left_size + t->count) {
return &t->key;
} else {
k -= left_size + t->count;
t = t->r;
}
}
return nullptr;
}
int count_impl(const Node* t, const T& key) const {
while (t != nullptr) {
if (comp(key, t->key)) {
t = t->l;
} else if (comp(t->key, key)) {
t = t->r;
} else {
return t->count;
}
}
return 0;
}
int order_of_key_impl(const Node* t, const T& key, bool upper) const {
int result = 0;
while (t != nullptr) {
const bool take = upper ? !comp(key, t->key) : comp(t->key, key);
if (take) {
result += subtree_size(t->l) + t->count;
t = t->r;
} else {
t = t->l;
}
}
return result;
}
const T* lower_bound_impl(const Node* t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != nullptr) {
const bool candidate = strict ? comp(key, t->key) : !comp(t->key, key);
if (candidate) {
result = &t->key;
t = t->l;
} else {
t = t->r;
}
}
return result;
}
const T* max_less_impl(const Node* t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != nullptr) {
const bool candidate = strict ? comp(t->key, key) : !comp(key, t->key);
if (candidate) {
result = &t->key;
t = t->r;
} else {
t = t->l;
}
}
return result;
}
static void dump_impl(const Node* t, std::vector<T>& result) {
if (t == nullptr) return;
dump_impl(t->l, result);
for (int i = 0; i < t->count; ++i) result.push_back(t->key);
dump_impl(t->r, result);
}
static void recycle_impl(Node* t) {
if (t == nullptr) return;
recycle_impl(t->l);
recycle_impl(t->r);
pool.recycle(t);
}
Node* clone_impl(const Node* t) {
if (t == nullptr) return nullptr;
Node* result = new_node(t->key, t->count);
result->l = clone_impl(t->l);
result->r = clone_impl(t->r);
update(result);
return result;
}
OrderedMultiset(Node* node, Compare compare) : root(node), comp(std::move(compare)) {}
public:
explicit OrderedMultiset(Compare compare) : root(nullptr), comp(std::move(compare)) {}
OrderedMultiset() : OrderedMultiset(Compare()) {}
OrderedMultiset(std::initializer_list<T> init, Compare compare = Compare())
: OrderedMultiset(std::move(compare)) {
for (const T& x : init) insert(x);
}
template <typename Iterator>
OrderedMultiset(Iterator first, Iterator last, Compare compare = Compare())
: OrderedMultiset(std::move(compare)) {
while (first != last) insert(*first++);
}
OrderedMultiset(const OrderedMultiset& other) : root(nullptr), comp(other.comp) {
root = clone_impl(other.root);
}
OrderedMultiset(OrderedMultiset&& other) noexcept
: root(std::exchange(other.root, nullptr)), comp(std::move(other.comp)) {}
~OrderedMultiset() {
recycle_impl(root);
}
OrderedMultiset& operator=(OrderedMultiset other) {
swap(other);
return *this;
}
void swap(OrderedMultiset& other) noexcept {
using std::swap;
swap(root, other.root);
swap(comp, other.comp);
}
int size() const { return subtree_size(root); }
int unique_size() const { return subtree_distinct_size(root); }
bool empty() const { return root == nullptr; }
void clear() {
recycle_impl(root);
root = nullptr;
}
void insert(T key, int multiplicity = 1) {
assert(multiplicity > 0);
bool new_key = false;
root = insert_impl(root, key, multiplicity, new_key);
}
bool erase_one(const T& key) {
int erased = 0;
bool removed_key = false;
root = erase_impl(root, key, false, erased, removed_key);
return erased != 0;
}
bool erase(const T& key) { return erase_one(key); }
int erase_all(const T& key) {
int erased = 0;
bool removed_key = false;
root = erase_impl(root, key, true, erased, removed_key);
return erased;
}
bool contains(const T& key) const { return count(key) > 0; }
int count(const T& key) const { return count_impl(root, key); }
const T* find_by_order(int k) const {
assert(0 <= k && k < size());
return kth_impl(root, k);
}
T kth(int k) const { return *find_by_order(k); }
int order_of_key(const T& key) const { return order_of_key_impl(root, key, false); }
int count_less(const T& key) const { return order_of_key(key); }
int count_less_equal(const T& key) const { return order_of_key_impl(root, key, true); }
int count_greater(const T& key) const { return size() - count_less_equal(key); }
int count_greater_equal(const T& key) const { return size() - count_less(key); }
const T* lower_bound(const T& key) const { return lower_bound_impl(root, key, false); }
const T* upper_bound(const T& key) const { return lower_bound_impl(root, key, true); }
const T* min_ge(const T& key) const { return lower_bound(key); }
const T* min_gt(const T& key) const { return upper_bound(key); }
const T* max_le(const T& key) const { return max_less_impl(root, key, false); }
const T* max_lt(const T& key) const { return max_less_impl(root, key, true); }
const T* min() const { return empty() ? nullptr : kth_impl(root, 0); }
const T* max() const { return empty() ? nullptr : kth_impl(root, size() - 1); }
std::pair<OrderedMultiset, OrderedMultiset> split(const T& key) && {
auto [l, r] = split_nodes(root, key);
root = nullptr;
return {OrderedMultiset(l, comp), OrderedMultiset(r, std::move(comp))};
}
OrderedMultiset merge(OrderedMultiset other) && {
assert(empty() || other.empty() || comp(*max(), *other.min()));
root = merge_nodes(root, other.root);
other.root = nullptr;
return std::move(*this);
}
std::vector<T> to_vector() const {
std::vector<T> result;
result.reserve(size());
dump_impl(root, result);
return result;
}
};
} // namespace ds
} // namespace m1une
#line 12 "ds/bst/rollback_ordered_multiset.hpp"
namespace m1une {
namespace ds {
template <class T, class Compare = std::less<T>>
struct RollbackOrderedMultiset {
private:
enum class Kind { key, clear, merge };
struct Entry {
Kind kind;
std::optional<T> key;
int old_count;
std::vector<T> values;
};
OrderedMultiset<T, Compare> _data;
std::vector<Entry> _history;
std::vector<std::size_t> _checkpoints;
void restore_count(const T& key, int count) {
_data.erase_all(key);
if (count > 0) _data.insert(key, count);
}
public:
explicit RollbackOrderedMultiset(Compare compare)
: _data(std::move(compare)) {}
RollbackOrderedMultiset() = default;
RollbackOrderedMultiset(
std::initializer_list<T> init,
Compare compare = Compare()
) : _data(init, std::move(compare)) {}
template <class Iterator>
RollbackOrderedMultiset(
Iterator first,
Iterator last,
Compare compare = Compare()
) : _data(first, last, std::move(compare)) {}
int size() const { return _data.size(); }
int unique_size() const { return _data.unique_size(); }
bool empty() const { return _data.empty(); }
std::size_t node_count() const { return std::size_t(unique_size()); }
void clear() {
if (_checkpoints.empty()) {
_data.clear();
return;
}
Entry entry{Kind::clear, std::nullopt, 0, {}};
entry.values = _data.to_vector();
_data.clear();
_history.push_back(std::move(entry));
}
void insert(T key, int multiplicity = 1) {
assert(multiplicity > 0);
if (_checkpoints.empty()) {
_data.insert(std::move(key), multiplicity);
return;
}
Entry entry{Kind::key, std::optional<T>(key), _data.count(key), {}};
_data.insert(std::move(key), multiplicity);
_history.push_back(std::move(entry));
}
void insert_inplace(T key, int multiplicity = 1) {
insert(std::move(key), multiplicity);
}
bool erase_one(const T& key) {
if (_checkpoints.empty()) return _data.erase_one(key);
int old_count = _data.count(key);
Entry entry{Kind::key, std::optional<T>(key), old_count, {}};
bool erased = _data.erase_one(key);
_history.push_back(std::move(entry));
return erased;
}
bool erase(const T& key) { return erase_one(key); }
bool erase_one_inplace(const T& key) { return erase_one(key); }
bool erase_inplace(const T& key) { return erase_one(key); }
int erase_all(const T& key) {
int old_count = _data.count(key);
if (_checkpoints.empty()) {
_data.erase_all(key);
return old_count;
}
Entry entry{Kind::key, std::optional<T>(key), old_count, {}};
_data.erase_all(key);
_history.push_back(std::move(entry));
return old_count;
}
bool erase_all_inplace(const T& key) { return erase_all(key) != 0; }
void merge(const RollbackOrderedMultiset& other) {
std::vector<T> values = other.to_vector();
for (const T& value : values) _data.insert(value);
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::merge, std::nullopt, 0, std::move(values)});
}
}
void merge(const OrderedMultiset<T, Compare>& other) {
std::vector<T> values = other.to_vector();
for (const T& value : values) _data.insert(value);
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::merge, std::nullopt, 0, std::move(values)});
}
}
bool contains(const T& key) const { return _data.contains(key); }
int count(const T& key) const { return _data.count(key); }
const T* find_by_order(int order) const { return _data.find_by_order(order); }
T kth(int order) const { return _data.kth(order); }
int order_of_key(const T& key) const { return _data.order_of_key(key); }
int count_less(const T& key) const { return _data.count_less(key); }
int count_less_equal(const T& key) const { return _data.count_less_equal(key); }
int count_greater(const T& key) const { return _data.count_greater(key); }
int count_greater_equal(const T& key) const { return _data.count_greater_equal(key); }
const T* lower_bound(const T& key) const { return _data.lower_bound(key); }
const T* upper_bound(const T& key) const { return _data.upper_bound(key); }
const T* min_ge(const T& key) const { return _data.min_ge(key); }
const T* min_gt(const T& key) const { return _data.min_gt(key); }
const T* max_le(const T& key) const { return _data.max_le(key); }
const T* max_lt(const T& key) const { return _data.max_lt(key); }
const T* min() const { return _data.min(); }
const T* max() const { return _data.max(); }
std::vector<T> to_vector() const { return _data.to_vector(); }
int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_checkpoints.reserve(count);
}
private:
void restore_one() {
Entry entry = std::move(_history.back());
_history.pop_back();
if (entry.kind == Kind::key) {
restore_count(*entry.key, entry.old_count);
} else if (entry.kind == Kind::clear) {
for (T& value : entry.values) _data.insert(std::move(value));
} else {
for (const T& value : entry.values) _data.erase_one(value);
}
}
public:
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() { _history.clear(); _checkpoints.clear(); }
void release() {
_data.clear();
_history.clear();
_checkpoints.clear();
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/bst/rollback_ordered_set.hpp"
#line 10 "ds/bst/rollback_ordered_set.hpp"
#line 1 "ds/bst/ordered_set.hpp"
#line 10 "ds/bst/ordered_set.hpp"
namespace m1une {
namespace ds {
template <typename T, typename Compare = std::less<T>>
struct OrderedSet {
private:
struct Node {
T key;
int size;
Node* l;
Node* r;
explicit Node(T value)
: key(std::move(value)), size(1), l(nullptr), r(nullptr) {}
};
static constexpr int pool_block_size = 1 << 15;
struct Pool {
std::vector<std::vector<Node>> blocks;
std::vector<Node*> free_nodes;
template <class... Args>
Node* emplace(Args&&... args) {
if (!free_nodes.empty()) {
Node* result = free_nodes.back();
free_nodes.pop_back();
std::destroy_at(result);
std::construct_at(result, std::forward<Args>(args)...);
return result;
}
if (blocks.empty() || int(blocks.back().size()) == pool_block_size) {
blocks.emplace_back();
blocks.back().reserve(pool_block_size);
}
blocks.back().emplace_back(std::forward<Args>(args)...);
return &blocks.back().back();
}
void recycle(Node* node) {
free_nodes.push_back(node);
}
};
inline static Pool pool;
Node* root;
Compare comp;
static int subtree_size(const Node* t) {
return t == nullptr ? 0 : t->size;
}
Node* new_node(T key) {
return pool.emplace(std::move(key));
}
static void update(Node* t) {
t->size = 1 + subtree_size(t->l) + subtree_size(t->r);
}
static Node* rotate_right(Node* t) {
Node* s = t->l;
t->l = s->r;
s->r = t;
update(t);
update(s);
return s;
}
static Node* rotate_left(Node* t) {
Node* s = t->r;
t->r = s->l;
s->l = t;
update(t);
update(s);
return s;
}
static Node* balance(Node* t) {
if (t == nullptr) return nullptr;
const int left_size = subtree_size(t->l);
const int right_size = subtree_size(t->r);
if (left_size + right_size > 1 && left_size > 3LL * right_size) {
if (subtree_size(t->l->r) >= 2LL * subtree_size(t->l->l)) {
t->l = rotate_left(t->l);
}
return rotate_right(t);
}
if (left_size + right_size > 1 && right_size > 3LL * left_size) {
if (subtree_size(t->r->l) >= 2LL * subtree_size(t->r->r)) {
t->r = rotate_right(t->r);
}
return rotate_left(t);
}
update(t);
return t;
}
static Node* join_with_root(Node* l, Node* middle, Node* r) {
const int left_size = subtree_size(l);
const int right_size = subtree_size(r);
if (left_size > 3LL * (right_size + 1)) {
l->r = join_with_root(l->r, middle, r);
return balance(l);
}
if (right_size > 3LL * (left_size + 1)) {
r->l = join_with_root(l, middle, r->l);
return balance(r);
}
middle->l = l;
middle->r = r;
return balance(middle);
}
static Node* detach_max(Node* t, Node*& maximum) {
if (t->r == nullptr) {
maximum = t;
return t->l;
}
t->r = detach_max(t->r, maximum);
return balance(t);
}
static Node* merge_nodes(Node* l, Node* r) {
if (l == nullptr || r == nullptr) return l == nullptr ? r : l;
Node* middle;
l = detach_max(l, middle);
return join_with_root(l, middle, r);
}
std::pair<Node*, Node*> split_nodes(Node* t, const T& key) {
if (t == nullptr) return {nullptr, nullptr};
Node* left = t->l;
Node* right = t->r;
t->l = nullptr;
t->r = nullptr;
if (comp(t->key, key)) {
auto [l, r] = split_nodes(right, key);
return {join_with_root(left, t, l), r};
}
auto [l, r] = split_nodes(left, key);
return {l, join_with_root(r, t, right)};
}
Node* insert_impl(Node* t, T& key, bool& inserted) {
if (t == nullptr) {
inserted = true;
return new_node(std::move(key));
}
if (comp(key, t->key)) {
t->l = insert_impl(t->l, key, inserted);
} else if (comp(t->key, key)) {
t->r = insert_impl(t->r, key, inserted);
} else {
return t;
}
if (!inserted) return t;
return balance(t);
}
Node* erase_impl(Node* t, const T& key, bool& erased) {
if (t == nullptr) return nullptr;
if (comp(key, t->key)) {
t->l = erase_impl(t->l, key, erased);
} else if (comp(t->key, key)) {
t->r = erase_impl(t->r, key, erased);
} else {
erased = true;
Node* l = t->l;
Node* r = t->r;
pool.recycle(t);
return merge_nodes(l, r);
}
if (!erased) return t;
return balance(t);
}
static const T* kth_impl(const Node* t, int k) {
while (t != nullptr) {
const int left_size = subtree_size(t->l);
if (k < left_size) {
t = t->l;
} else if (k == left_size) {
return &t->key;
} else {
k -= left_size + 1;
t = t->r;
}
}
return nullptr;
}
int order_of_key_impl(const Node* t, const T& key, bool upper) const {
int result = 0;
while (t != nullptr) {
const bool take = upper ? !comp(key, t->key) : comp(t->key, key);
if (take) {
result += subtree_size(t->l) + 1;
t = t->r;
} else {
t = t->l;
}
}
return result;
}
const T* lower_bound_impl(const Node* t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != nullptr) {
const bool candidate = strict ? comp(key, t->key) : !comp(t->key, key);
if (candidate) {
result = &t->key;
t = t->l;
} else {
t = t->r;
}
}
return result;
}
const T* max_less_impl(const Node* t, const T& key, bool strict) const {
const T* result = nullptr;
while (t != nullptr) {
const bool candidate = strict ? comp(t->key, key) : !comp(key, t->key);
if (candidate) {
result = &t->key;
t = t->r;
} else {
t = t->l;
}
}
return result;
}
bool contains_impl(const Node* t, const T& key) const {
while (t != nullptr) {
if (comp(key, t->key)) {
t = t->l;
} else if (comp(t->key, key)) {
t = t->r;
} else {
return true;
}
}
return false;
}
static void dump_impl(const Node* t, std::vector<T>& result) {
if (t == nullptr) return;
dump_impl(t->l, result);
result.push_back(t->key);
dump_impl(t->r, result);
}
static void recycle_impl(Node* t) {
if (t == nullptr) return;
recycle_impl(t->l);
recycle_impl(t->r);
pool.recycle(t);
}
Node* clone_impl(const Node* t) {
if (t == nullptr) return nullptr;
Node* result = new_node(t->key);
result->l = clone_impl(t->l);
result->r = clone_impl(t->r);
update(result);
return result;
}
OrderedSet(Node* node, Compare compare) : root(node), comp(std::move(compare)) {}
public:
explicit OrderedSet(Compare compare)
: root(nullptr), comp(std::move(compare)) {}
OrderedSet() : OrderedSet(Compare()) {}
OrderedSet(std::initializer_list<T> init, Compare compare = Compare()) : OrderedSet(std::move(compare)) {
for (const T& x : init) insert(x);
}
template <typename Iterator>
OrderedSet(Iterator first, Iterator last, Compare compare = Compare()) : OrderedSet(std::move(compare)) {
while (first != last) insert(*first++);
}
OrderedSet(const OrderedSet& other)
: root(nullptr), comp(other.comp) {
root = clone_impl(other.root);
}
OrderedSet(OrderedSet&& other) noexcept
: root(std::exchange(other.root, nullptr)), comp(std::move(other.comp)) {}
~OrderedSet() {
recycle_impl(root);
}
OrderedSet& operator=(OrderedSet other) {
swap(other);
return *this;
}
void swap(OrderedSet& other) noexcept {
using std::swap;
swap(root, other.root);
swap(comp, other.comp);
}
int size() const { return subtree_size(root); }
int unique_size() const { return size(); }
bool empty() const { return root == nullptr; }
void clear() {
recycle_impl(root);
root = nullptr;
}
bool insert(T key) {
bool inserted = false;
root = insert_impl(root, key, inserted);
return inserted;
}
bool erase(const T& key) {
bool erased = false;
root = erase_impl(root, key, erased);
return erased;
}
bool contains(const T& key) const { return contains_impl(root, key); }
int count(const T& key) const { return contains(key) ? 1 : 0; }
const T* find_by_order(int k) const {
assert(0 <= k && k < size());
return kth_impl(root, k);
}
T kth(int k) const { return *find_by_order(k); }
int order_of_key(const T& key) const { return order_of_key_impl(root, key, false); }
int count_less(const T& key) const { return order_of_key(key); }
int count_less_equal(const T& key) const { return order_of_key_impl(root, key, true); }
int count_greater(const T& key) const { return size() - count_less_equal(key); }
int count_greater_equal(const T& key) const { return size() - count_less(key); }
const T* lower_bound(const T& key) const { return lower_bound_impl(root, key, false); }
const T* upper_bound(const T& key) const { return lower_bound_impl(root, key, true); }
const T* min_ge(const T& key) const { return lower_bound(key); }
const T* min_gt(const T& key) const { return upper_bound(key); }
const T* max_le(const T& key) const { return max_less_impl(root, key, false); }
const T* max_lt(const T& key) const { return max_less_impl(root, key, true); }
const T* min() const { return empty() ? nullptr : kth_impl(root, 0); }
const T* max() const { return empty() ? nullptr : kth_impl(root, size() - 1); }
std::pair<OrderedSet, OrderedSet> split(const T& key) && {
auto [l, r] = split_nodes(root, key);
root = nullptr;
return {OrderedSet(l, comp), OrderedSet(r, std::move(comp))};
}
OrderedSet merge(OrderedSet other) && {
assert(empty() || other.empty() || comp(*max(), *other.min()));
root = merge_nodes(root, other.root);
other.root = nullptr;
return std::move(*this);
}
std::vector<T> to_vector() const {
std::vector<T> result;
result.reserve(size());
dump_impl(root, result);
return result;
}
};
} // namespace ds
} // namespace m1une
#line 12 "ds/bst/rollback_ordered_set.hpp"
namespace m1une {
namespace ds {
template <class T, class Compare = std::less<T>>
struct RollbackOrderedSet {
private:
enum class Kind { insert, erase, clear, merge };
struct Entry {
Kind kind;
bool changed;
std::optional<T> key;
std::vector<T> keys;
};
OrderedSet<T, Compare> _data;
std::vector<Entry> _history;
std::vector<std::size_t> _checkpoints;
public:
explicit RollbackOrderedSet(Compare compare)
: _data(std::move(compare)) {}
RollbackOrderedSet() = default;
RollbackOrderedSet(
std::initializer_list<T> init,
Compare compare = Compare()
) : _data(init, std::move(compare)) {}
template <class Iterator>
RollbackOrderedSet(
Iterator first,
Iterator last,
Compare compare = Compare()
) : _data(first, last, std::move(compare)) {}
int size() const { return _data.size(); }
int unique_size() const { return _data.size(); }
bool empty() const { return _data.empty(); }
std::size_t node_count() const { return std::size_t(size()); }
void clear() {
if (_checkpoints.empty()) {
_data.clear();
return;
}
Entry entry{Kind::clear, !empty(), std::nullopt, {}};
if (!empty()) entry.keys = _data.to_vector();
_data.clear();
_history.push_back(std::move(entry));
}
bool insert(T key) {
if (_checkpoints.empty()) return _data.insert(std::move(key));
bool changed = !_data.contains(key);
Entry entry{Kind::insert, changed, std::nullopt, {}};
if (changed) entry.key.emplace(key);
_data.insert(std::move(key));
_history.push_back(std::move(entry));
return changed;
}
bool erase(const T& key) {
if (_checkpoints.empty()) return _data.erase(key);
bool changed = _data.contains(key);
Entry entry{Kind::erase, changed, std::nullopt, {}};
if (changed) entry.key.emplace(key);
_data.erase(key);
_history.push_back(std::move(entry));
return changed;
}
void merge(const RollbackOrderedSet& other) {
std::vector<T> keys = other.to_vector();
for (const T& key : keys) {
bool inserted = _data.insert(key);
assert(inserted);
}
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::merge, !keys.empty(), std::nullopt, std::move(keys)});
}
}
void merge(const OrderedSet<T, Compare>& other) {
std::vector<T> keys = other.to_vector();
for (const T& key : keys) {
bool inserted = _data.insert(key);
assert(inserted);
}
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::merge, !keys.empty(), std::nullopt, std::move(keys)});
}
}
bool contains(const T& key) const { return _data.contains(key); }
int count(const T& key) const { return _data.count(key); }
const T* find_by_order(int order) const { return _data.find_by_order(order); }
T kth(int order) const { return _data.kth(order); }
int order_of_key(const T& key) const { return _data.order_of_key(key); }
int count_less(const T& key) const { return _data.count_less(key); }
int count_less_equal(const T& key) const { return _data.count_less_equal(key); }
int count_greater(const T& key) const { return _data.count_greater(key); }
int count_greater_equal(const T& key) const { return _data.count_greater_equal(key); }
const T* lower_bound(const T& key) const { return _data.lower_bound(key); }
const T* upper_bound(const T& key) const { return _data.upper_bound(key); }
const T* min_ge(const T& key) const { return _data.min_ge(key); }
const T* min_gt(const T& key) const { return _data.min_gt(key); }
const T* max_le(const T& key) const { return _data.max_le(key); }
const T* max_lt(const T& key) const { return _data.max_lt(key); }
const T* min() const { return _data.min(); }
const T* max() const { return _data.max(); }
std::vector<T> to_vector() const { return _data.to_vector(); }
int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_checkpoints.reserve(count);
}
private:
void restore_one() {
Entry entry = std::move(_history.back());
_history.pop_back();
if (!entry.changed) return;
if (entry.kind == Kind::insert) {
_data.erase(*entry.key);
} else if (entry.kind == Kind::erase) {
_data.insert(std::move(*entry.key));
} else if (entry.kind == Kind::clear) {
for (T& key : entry.keys) _data.insert(std::move(key));
} else {
for (const T& key : entry.keys) _data.erase(key);
}
}
public:
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() { _history.clear(); _checkpoints.clear(); }
void release() {
_data.clear();
_history.clear();
_checkpoints.clear();
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/deque/rollback_deque.hpp"
#line 5 "ds/deque/rollback_deque.hpp"
#include <deque>
#line 9 "ds/deque/rollback_deque.hpp"
namespace m1une {
namespace ds {
template <class T>
struct RollbackDeque {
private:
enum class Kind { push_front, push_back, pop_front, pop_back, clear };
struct Entry {
Kind kind;
std::optional<T> value;
std::deque<T> values;
};
std::deque<T> _values;
std::vector<Entry> _history;
std::vector<std::size_t> _checkpoints;
std::size_t _stored_values = 0;
void record_push(Kind kind) {
if (!_checkpoints.empty()) _history.push_back(Entry{kind, std::nullopt, {}});
++_stored_values;
}
public:
RollbackDeque() = default;
int size() const { return int(_values.size()); }
bool empty() const { return _values.empty(); }
std::size_t node_count() const { return _stored_values; }
const T& front() const {
assert(!empty());
return _values.front();
}
const T& back() const {
assert(!empty());
return _values.back();
}
void push_front(T value) {
record_push(Kind::push_front);
_values.push_front(std::move(value));
}
template <class... Args>
void emplace_front(Args&&... args) {
record_push(Kind::push_front);
_values.emplace_front(std::forward<Args>(args)...);
}
void push_back(T value) {
record_push(Kind::push_back);
_values.push_back(std::move(value));
}
template <class... Args>
void emplace_back(Args&&... args) {
record_push(Kind::push_back);
_values.emplace_back(std::forward<Args>(args)...);
}
void pop_front() {
assert(!empty());
if (_checkpoints.empty()) {
_values.pop_front();
--_stored_values;
} else {
Entry entry{Kind::pop_front, std::nullopt, {}};
entry.value.emplace(std::move(_values.front()));
_values.pop_front();
_history.push_back(std::move(entry));
}
}
void pop_back() {
assert(!empty());
if (_checkpoints.empty()) {
_values.pop_back();
--_stored_values;
} else {
Entry entry{Kind::pop_back, std::nullopt, {}};
entry.value.emplace(std::move(_values.back()));
_values.pop_back();
_history.push_back(std::move(entry));
}
}
void clear() {
if (_checkpoints.empty()) {
_stored_values -= _values.size();
_values.clear();
} else {
Entry entry{Kind::clear, std::nullopt, {}};
entry.values = std::move(_values);
_values.clear();
_history.push_back(std::move(entry));
}
}
int snapshot() {
_checkpoints.push_back(_history.size());
return int(_checkpoints.size());
}
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_checkpoints.reserve(count);
}
private:
void restore_one() {
Entry entry = std::move(_history.back());
_history.pop_back();
if (entry.kind == Kind::push_front) {
_values.pop_front();
--_stored_values;
} else if (entry.kind == Kind::push_back) {
_values.pop_back();
--_stored_values;
} else if (entry.kind == Kind::pop_front) {
_values.push_front(std::move(*entry.value));
} else if (entry.kind == Kind::pop_back) {
_values.push_back(std::move(*entry.value));
} else {
_values = std::move(entry.values);
}
}
public:
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() {
for (const Entry& entry : _history) {
if (entry.value) --_stored_values;
_stored_values -= entry.values.size();
}
_history.clear();
_checkpoints.clear();
}
void release() {
_values.clear();
_history.clear();
_checkpoints.clear();
_stored_values = 0;
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/dsu/rollback_potentialized_dsu.hpp"
#include <algorithm>
#line 6 "ds/dsu/rollback_potentialized_dsu.hpp"
#include <concepts>
#include <cstddef>
#line 10 "ds/dsu/rollback_potentialized_dsu.hpp"
#line 1 "monoid/concept.hpp"
#line 5 "monoid/concept.hpp"
namespace m1une {
namespace monoid {
// Concept to check if a type satisfies the requirements of a Monoid.
// A Monoid must have a `value_type`, an identity element `id()`, and an associative binary operation `op()`.
template <typename M>
concept IsMonoid = requires(typename M::value_type a, typename M::value_type b) {
// 1. Must define `value_type`
typename M::value_type;
// 2. Must have a static method `id()` returning `value_type`
{ M::id() } -> std::same_as<typename M::value_type>;
// 3. Must have a static method `op(a, b)` returning `value_type`
{ M::op(a, b) } -> std::same_as<typename M::value_type>;
};
// Concept for groups. A type satisfying this concept must also obey the group
// laws; concepts can check the interface but not the algebraic properties.
template <typename M>
concept IsGroup = IsMonoid<M> && requires(typename M::value_type a) {
{ M::inv(a) } -> std::same_as<typename M::value_type>;
};
// Concept for commutative groups. Commutativity is a semantic requirement and
// cannot be checked by a C++ concept.
template <typename M>
concept IsCommutativeGroup = IsGroup<M>;
} // namespace monoid
} // namespace m1une
#line 12 "ds/dsu/rollback_potentialized_dsu.hpp"
namespace m1une {
namespace ds {
template <m1une::monoid::IsGroup Group>
requires std::equality_comparable<typename Group::value_type>
struct RollbackPotentializedDsu {
using T = typename Group::value_type;
private:
struct HistoryEntry {
int first;
int first_value;
int second;
int second_value;
T second_diff;
HistoryEntry(int first_index, int first_parent, int second_index,
int second_parent, T diff)
: first(first_index),
first_value(first_parent),
second(second_index),
second_value(second_parent),
second_diff(std::move(diff)) {}
};
int _n;
int _component_count;
std::vector<int> _parent_or_size;
std::vector<T> _diff_to_parent;
std::vector<HistoryEntry> _history;
std::vector<std::size_t> _checkpoints;
static int check_size(int n) {
assert(0 <= n);
return n;
}
std::pair<int, T> leader_and_potential(int vertex) const {
assert(0 <= vertex && vertex < _n);
T result = Group::id();
while (_parent_or_size[vertex] >= 0) {
result = Group::op(_diff_to_parent[vertex], result);
vertex = _parent_or_size[vertex];
}
return {vertex, std::move(result)};
}
public:
RollbackPotentializedDsu() : RollbackPotentializedDsu(0) {}
explicit RollbackPotentializedDsu(int n)
: _n(check_size(n)),
_component_count(_n),
_parent_or_size(_n, -1),
_diff_to_parent(_n, Group::id()) {}
int size() const { return _n; }
bool empty() const { return _n == 0; }
int component_count() const { return _component_count; }
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_checkpoints.reserve(count);
}
int leader(int vertex) const {
return leader_and_potential(vertex).first;
}
bool same(int first, int second) const {
return leader(first) == leader(second);
}
int group_size(int vertex) const {
return -_parent_or_size[leader(vertex)];
}
int size(int vertex) const { return group_size(vertex); }
T potential(int vertex) const {
return leader_and_potential(vertex).second;
}
T diff(int first, int second) const {
assert(same(first, second));
return Group::op(Group::inv(potential(first)), potential(second));
}
int parent_or_size(int vertex) const {
assert(0 <= vertex && vertex < _n);
return _parent_or_size[vertex];
}
bool merge(int first, int second, const T& difference) {
auto [first_root, first_potential] = leader_and_potential(first);
auto [second_root, second_potential] = leader_and_potential(second);
if (first_root == second_root) {
return Group::op(Group::inv(first_potential), second_potential) == difference;
}
T second_from_first = Group::op(
Group::op(first_potential, difference),
Group::inv(second_potential)
);
if (-_parent_or_size[first_root] < -_parent_or_size[second_root]) {
std::swap(first_root, second_root);
second_from_first = Group::inv(second_from_first);
}
if (!_checkpoints.empty()) {
_history.emplace_back(
first_root, _parent_or_size[first_root], second_root,
_parent_or_size[second_root], _diff_to_parent[second_root]
);
}
_parent_or_size[first_root] += _parent_or_size[second_root];
_parent_or_size[second_root] = first_root;
_diff_to_parent[second_root] = std::move(second_from_first);
--_component_count;
return true;
}
private:
void restore_one() {
HistoryEntry entry = std::move(_history.back());
_history.pop_back();
_parent_or_size[entry.first] = entry.first_value;
_parent_or_size[entry.second] = entry.second_value;
_diff_to_parent[entry.second] = std::move(entry.second_diff);
++_component_count;
}
public:
int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() { _history.clear(); _checkpoints.clear(); }
std::vector<std::vector<int>> groups() const {
std::vector<int> leaders(_n);
std::vector<int> sizes(_n);
for (int vertex = 0; vertex < _n; ++vertex) {
leaders[vertex] = leader(vertex);
++sizes[leaders[vertex]];
}
std::vector<std::vector<int>> result(_n);
for (int vertex = 0; vertex < _n; ++vertex) {
result[vertex].reserve(sizes[vertex]);
}
for (int vertex = 0; vertex < _n; ++vertex) {
result[leaders[vertex]].push_back(vertex);
}
result.erase(
std::remove_if(
result.begin(), result.end(),
[](const std::vector<int>& group) { return group.empty(); }
),
result.end()
);
return result;
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/dynamic_array/rollback_dynamic_array.hpp"
#line 9 "ds/dynamic_array/rollback_dynamic_array.hpp"
#line 1 "ds/dynamic_array/dynamic_array.hpp"
#line 5 "ds/dynamic_array/dynamic_array.hpp"
#include <chrono>
#include <cstdint>
#line 10 "ds/dynamic_array/dynamic_array.hpp"
namespace m1une {
namespace ds {
template <typename T>
struct DynamicArray {
private:
struct Node {
T val;
int priority;
int count;
int l, r;
bool rev;
Node() : val(T()), priority(0), count(0), l(0), r(0), rev(false) {}
Node(T value, int node_priority)
: val(std::move(value)), priority(node_priority), count(1), l(0), r(0), rev(false) {}
};
std::vector<Node> pool;
int root;
std::uint32_t rng_state;
int new_node(T val) {
pool.push_back(Node(std::move(val), next_priority()));
return pool.size() - 1;
}
int next_priority() {
rng_state ^= rng_state << 13;
rng_state ^= rng_state >> 17;
rng_state ^= rng_state << 5;
return int(rng_state);
}
void update(int t) {
if (t) {
pool[t].count = 1 + pool[pool[t].l].count + pool[pool[t].r].count;
}
}
void apply_reverse(int t) {
if (t) {
pool[t].rev = !pool[t].rev;
}
}
void push(int t) {
if (!t || !pool[t].rev) return;
std::swap(pool[t].l, pool[t].r);
apply_reverse(pool[t].l);
apply_reverse(pool[t].r);
pool[t].rev = false;
}
void split(int t, int pos, int& l, int& r) {
if (!t) {
l = r = 0;
return;
}
if (pos == 0) {
l = 0;
r = t;
return;
}
if (pos == pool[t].count) {
l = t;
r = 0;
return;
}
push(t);
int left_count = pool[pool[t].l].count;
if (pos == left_count) {
l = pool[t].l;
pool[t].l = 0;
update(t);
r = t;
return;
}
if (pos == left_count + 1) {
r = pool[t].r;
pool[t].r = 0;
update(t);
l = t;
return;
}
if (pos <= left_count) {
split(pool[t].l, pos, l, pool[t].l);
r = t;
} else {
split(pool[t].r, pos - left_count - 1, pool[t].r, r);
l = t;
}
update(t);
}
int merge(int l, int r) {
if (!l || !r) return l ? l : r;
if (pool[l].priority > pool[r].priority) {
push(l);
if (pool[l].r) {
pool[l].r = merge(pool[l].r, r);
} else {
pool[l].r = r;
}
update(l);
return l;
} else {
push(r);
if (pool[r].l) {
pool[r].l = merge(l, pool[r].l);
} else {
pool[r].l = l;
}
update(r);
return r;
}
}
int insert_node(int t, int pos, int node) {
if (!t) return node;
if (pool[node].priority > pool[t].priority) {
split(t, pos, pool[node].l, pool[node].r);
update(node);
return node;
}
push(t);
int left_count = pool[pool[t].l].count;
if (pos <= left_count) {
pool[t].l = insert_node(pool[t].l, pos, node);
} else {
pool[t].r = insert_node(pool[t].r, pos - left_count - 1, node);
}
update(t);
return t;
}
int erase_node(int t, int pos) {
push(t);
int left_count = pool[pool[t].l].count;
if (pos < left_count) {
pool[t].l = erase_node(pool[t].l, pos);
update(t);
return t;
}
if (pos == left_count) {
return merge(pool[t].l, pool[t].r);
}
pool[t].r = erase_node(pool[t].r, pos - left_count - 1);
update(t);
return t;
}
int find_node(int t, int pos) {
while (t) {
push(t);
int left_count = pool[pool[t].l].count;
if (pos < left_count) {
t = pool[t].l;
} else if (pos == left_count) {
return t;
} else {
pos -= left_count + 1;
t = pool[t].r;
}
}
return 0;
}
int find_node(int t, int pos, bool reversed) const {
while (t) {
bool cur_reversed = reversed ^ pool[t].rev;
int left = cur_reversed ? pool[t].r : pool[t].l;
int right = cur_reversed ? pool[t].l : pool[t].r;
int left_count = pool[left].count;
if (pos < left_count) {
t = left;
reversed = cur_reversed;
} else if (pos == left_count) {
return t;
} else {
pos -= left_count + 1;
t = right;
reversed = cur_reversed;
}
}
return 0;
}
void dump_dfs(int t, std::vector<T>& res, bool reversed = false) const {
if (!t) return;
bool cur_reversed = reversed ^ pool[t].rev;
int left = cur_reversed ? pool[t].r : pool[t].l;
int right = cur_reversed ? pool[t].l : pool[t].r;
dump_dfs(left, res, cur_reversed);
res.push_back(pool[t].val);
dump_dfs(right, res, cur_reversed);
}
void dump_range_dfs(int t, int ql, int qr, int offset, std::vector<T>& res, bool reversed = false) const {
if (!t || qr <= offset || offset + pool[t].count <= ql) return;
bool cur_reversed = reversed ^ pool[t].rev;
int left = cur_reversed ? pool[t].r : pool[t].l;
int right = cur_reversed ? pool[t].l : pool[t].r;
int left_count = pool[left].count;
int node_pos = offset + left_count;
dump_range_dfs(left, ql, qr, offset, res, cur_reversed);
if (ql <= node_pos && node_pos < qr) {
res.push_back(pool[t].val);
}
dump_range_dfs(right, ql, qr, node_pos + 1, res, cur_reversed);
}
int clone_subtree_from(const DynamicArray& other, int t) {
if (!t) return 0;
int res = static_cast<int>(pool.size());
pool.push_back(other.pool[t]);
pool[res].l = clone_subtree_from(other, other.pool[t].l);
pool[res].r = clone_subtree_from(other, other.pool[t].r);
return res;
}
void update_dfs(int t) {
if (!t) return;
update_dfs(pool[t].l);
update_dfs(pool[t].r);
update(t);
}
int build_cartesian(int first, int last) {
if (first == last) return 0;
std::vector<int> stack;
stack.reserve(last - first);
for (int i = first; i < last; i++) {
int left_child = 0;
while (!stack.empty() && pool[stack.back()].priority < pool[i].priority) {
left_child = stack.back();
stack.pop_back();
}
pool[i].l = left_child;
if (!stack.empty()) {
pool[stack.back()].r = i;
}
stack.push_back(i);
}
int res = stack.front();
update_dfs(res);
return res;
}
int build_from_vector(const std::vector<T>& v) {
int first = int(pool.size());
pool.reserve(pool.size() + v.size());
for (const T& x : v) {
new_node(x);
}
return build_cartesian(first, int(pool.size()));
}
int build_from_vector(std::vector<T>&& v) {
int first = int(pool.size());
pool.reserve(pool.size() + v.size());
for (T& x : v) {
new_node(std::move(x));
}
return build_cartesian(first, int(pool.size()));
}
void reset_to_empty() {
pool.clear();
pool.push_back(Node());
root = 0;
}
public:
DynamicArray() : root(0), rng_state(std::uint32_t(std::chrono::steady_clock::now().time_since_epoch().count())) {
pool.push_back(Node());
if (rng_state == 0) rng_state = 1;
}
DynamicArray(const DynamicArray& other) : pool(other.pool), root(other.root), rng_state(other.rng_state) {}
DynamicArray(DynamicArray&& other) noexcept
: pool(std::move(other.pool)), root(other.root), rng_state(other.rng_state) {
other.reset_to_empty();
}
DynamicArray& operator=(const DynamicArray& other) {
if (this != &other) {
pool = other.pool;
root = other.root;
rng_state = other.rng_state;
}
return *this;
}
DynamicArray& operator=(DynamicArray&& other) noexcept {
if (this != &other) {
pool = std::move(other.pool);
root = other.root;
rng_state = other.rng_state;
other.reset_to_empty();
}
return *this;
}
explicit DynamicArray(int n) : DynamicArray(n, T()) {}
DynamicArray(int n, const T& value) : DynamicArray() {
assert(0 <= n);
pool.reserve(n + 1);
int first = int(pool.size());
for (int i = 0; i < n; i++) {
new_node(value);
}
root = build_cartesian(first, int(pool.size()));
}
explicit DynamicArray(const std::vector<T>& v) : DynamicArray() {
pool.reserve(v.size() + 1);
root = build_from_vector(v);
}
explicit DynamicArray(std::vector<T>&& v) : DynamicArray() {
pool.reserve(v.size() + 1);
root = build_from_vector(std::move(v));
}
DynamicArray(std::initializer_list<T> init) : DynamicArray() {
pool.reserve(init.size() + 1);
for (const T& x : init) push_back(x);
}
int size() const {
return pool[root].count;
}
bool empty() const {
return size() == 0;
}
void clear() {
reset_to_empty();
}
void insert(int pos, T val) {
assert(0 <= pos && pos <= size());
root = insert_node(root, pos, new_node(std::move(val)));
}
void insert(int pos, const std::vector<T>& v) {
assert(0 <= pos && pos <= size());
pool.reserve(pool.size() + v.size());
int mid = build_from_vector(v);
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void insert(int pos, std::vector<T>&& v) {
assert(0 <= pos && pos <= size());
pool.reserve(pool.size() + v.size());
int mid = build_from_vector(std::move(v));
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void insert(int pos, std::initializer_list<T> init) {
insert(pos, std::vector<T>(init));
}
void insert(int pos, const DynamicArray& other) {
assert(0 <= pos && pos <= size());
if (other.empty()) return;
pool.reserve(pool.size() + other.size());
int mid = clone_subtree_from(other, other.root);
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void push_back(T val) {
insert(size(), std::move(val));
}
void push_front(T val) {
insert(0, std::move(val));
}
void append(const std::vector<T>& v) {
insert(size(), v);
}
void append(std::vector<T>&& v) {
insert(size(), std::move(v));
}
void append(const DynamicArray& other) {
insert(size(), other);
}
void erase(int pos) {
assert(0 <= pos && pos < size());
root = erase_node(root, pos);
}
void erase(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return;
int a, b, c;
split(root, l, a, b);
split(b, r - l, b, c);
root = merge(a, c);
}
void pop_back() {
assert(!empty());
erase(size() - 1);
}
void pop_front() {
assert(!empty());
erase(0);
}
T& at(int pos) {
assert(0 <= pos && pos < size());
return pool[find_node(root, pos)].val;
}
const T& at(int pos) const {
assert(0 <= pos && pos < size());
return pool[find_node(root, pos, false)].val;
}
T& operator[](int pos) {
return at(pos);
}
const T& operator[](int pos) const {
return at(pos);
}
T& front() {
assert(!empty());
return at(0);
}
const T& front() const {
assert(!empty());
return at(0);
}
T& back() {
assert(!empty());
return at(size() - 1);
}
const T& back() const {
assert(!empty());
return at(size() - 1);
}
void reverse(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return;
int a, b, c;
split(root, l, a, b);
split(b, r - l, b, c);
apply_reverse(b);
root = merge(merge(a, b), c);
}
void reverse() {
apply_reverse(root);
}
void rotate(int l, int m, int r) {
assert(0 <= l && l <= m && m <= r && r <= size());
if (l == m || m == r) return;
int a, b, c, d;
split(root, l, a, b);
split(b, m - l, b, c);
split(c, r - m, c, d);
root = merge(merge(a, c), merge(b, d));
}
T get(int pos) const {
return at(pos);
}
void set(int pos, T val) {
at(pos) = std::move(val);
}
std::vector<T> to_vector() const {
std::vector<T> res;
res.reserve(size());
dump_dfs(root, res);
return res;
}
std::vector<T> to_vector(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
std::vector<T> res;
res.reserve(r - l);
dump_range_dfs(root, l, r, 0, res);
return res;
}
DynamicArray split_off(int pos) {
assert(0 <= pos && pos <= size());
int l, r;
split(root, pos, l, r);
root = l;
DynamicArray res;
res.pool.reserve(pool[r].count + 1);
res.root = res.clone_subtree_from(*this, r);
return res;
}
};
} // namespace ds
} // namespace m1une
#line 11 "ds/dynamic_array/rollback_dynamic_array.hpp"
namespace m1une {
namespace ds {
template <class T>
struct RollbackDynamicArray {
private:
enum class Kind { insert, erase, set, reverse, rotate, clear };
struct Entry {
Kind kind;
int first;
int second;
int third;
std::optional<T> value;
std::vector<T> values;
};
DynamicArray<T> _data;
std::vector<Entry> _history;
std::vector<std::size_t> _checkpoints;
void record_insert(int pos, int count) {
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::insert, pos, count, 0, std::nullopt, {}});
}
}
public:
RollbackDynamicArray() = default;
explicit RollbackDynamicArray(int n) : _data(n) {}
RollbackDynamicArray(int n, const T& value) : _data(n, value) {}
explicit RollbackDynamicArray(const std::vector<T>& values) : _data(values) {}
explicit RollbackDynamicArray(std::vector<T>&& values) : _data(std::move(values)) {}
RollbackDynamicArray(std::initializer_list<T> init) : _data(init) {}
int size() const { return _data.size(); }
bool empty() const { return _data.empty(); }
std::size_t node_count() const { return std::size_t(size()); }
void clear() {
Entry entry{Kind::clear, 0, 0, 0, std::nullopt, {}};
if (!_checkpoints.empty()) entry.values = _data.to_vector();
_data.clear();
if (!_checkpoints.empty()) _history.push_back(std::move(entry));
}
void insert(int pos, T value) {
_data.insert(pos, std::move(value));
record_insert(pos, 1);
}
void insert(int pos, const std::vector<T>& values) {
_data.insert(pos, values);
record_insert(pos, int(values.size()));
}
void insert(int pos, std::vector<T>&& values) {
int count = int(values.size());
_data.insert(pos, std::move(values));
record_insert(pos, count);
}
void insert(int pos, std::initializer_list<T> values) {
insert(pos, std::vector<T>(values));
}
void insert(int pos, const RollbackDynamicArray& other) {
insert(pos, other.to_vector());
}
void insert(int pos, const DynamicArray<T>& other) {
insert(pos, other.to_vector());
}
void push_back(T value) { insert(size(), std::move(value)); }
void push_front(T value) { insert(0, std::move(value)); }
void append(const std::vector<T>& values) { insert(size(), values); }
void append(std::vector<T>&& values) { insert(size(), std::move(values)); }
void append(const RollbackDynamicArray& other) { insert(size(), other); }
void append(const DynamicArray<T>& other) { insert(size(), other); }
void erase(int pos) { erase(pos, pos + 1); }
void erase(int left, int right) {
assert(0 <= left && left <= right && right <= size());
Entry entry{Kind::erase, left, 0, 0, std::nullopt, {}};
if (!_checkpoints.empty()) entry.values = _data.to_vector(left, right);
_data.erase(left, right);
if (!_checkpoints.empty()) _history.push_back(std::move(entry));
}
void pop_back() {
assert(!empty());
erase(size() - 1);
}
void pop_front() {
assert(!empty());
erase(0);
}
const T& at(int pos) const { return _data.at(pos); }
const T& operator[](int pos) const { return _data[pos]; }
const T& front() const { return _data.front(); }
const T& back() const { return _data.back(); }
T get(int pos) const { return _data.get(pos); }
void set(int pos, T value) {
Entry entry{Kind::set, pos, 0, 0, std::nullopt, {}};
if (!_checkpoints.empty()) entry.value.emplace(_data.get(pos));
_data.set(pos, std::move(value));
if (!_checkpoints.empty()) _history.push_back(std::move(entry));
}
void set_inplace(int pos, T value) { set(pos, std::move(value)); }
void reverse(int left, int right) {
_data.reverse(left, right);
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::reverse, left, right, 0, std::nullopt, {}});
}
}
void reverse() { reverse(0, size()); }
void rotate(int left, int middle, int right) {
_data.rotate(left, middle, right);
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::rotate, left, middle, right, std::nullopt, {}});
}
}
std::vector<T> to_vector() const { return _data.to_vector(); }
std::vector<T> to_vector(int left, int right) const { return _data.to_vector(left, right); }
std::pair<DynamicArray<T>, DynamicArray<T>> split(int pos) const {
assert(0 <= pos && pos <= size());
DynamicArray<T> left = _data;
DynamicArray<T> right = left.split_off(pos);
return {std::move(left), std::move(right)};
}
DynamicArray<T> split_off(int pos) const {
return split(pos).second;
}
int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_checkpoints.reserve(count);
}
private:
void restore_one() {
Entry entry = std::move(_history.back());
_history.pop_back();
if (entry.kind == Kind::insert) {
_data.erase(entry.first, entry.first + entry.second);
} else if (entry.kind == Kind::erase) {
_data.insert(entry.first, std::move(entry.values));
} else if (entry.kind == Kind::set) {
_data.set(entry.first, std::move(*entry.value));
} else if (entry.kind == Kind::reverse) {
_data.reverse(entry.first, entry.second);
} else if (entry.kind == Kind::rotate) {
int new_middle = entry.first + entry.third - entry.second;
_data.rotate(entry.first, new_middle, entry.third);
} else {
_data.insert(0, std::move(entry.values));
}
}
public:
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() { _history.clear(); _checkpoints.clear(); }
void release() {
_data.clear();
_history.clear();
_checkpoints.clear();
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/dynamic_array/rollback_dynamic_lazy_monoid_array.hpp"
#line 9 "ds/dynamic_array/rollback_dynamic_lazy_monoid_array.hpp"
#include <type_traits>
#line 12 "ds/dynamic_array/rollback_dynamic_lazy_monoid_array.hpp"
#line 1 "acted_monoid/concept.hpp"
#line 5 "acted_monoid/concept.hpp"
namespace m1une {
namespace acted_monoid {
// Concept defining the requirements for an Acted Monoid.
template <typename AM>
concept IsActedMonoid = requires(typename AM::value_type a, typename AM::value_type b, typename AM::operator_type f,
typename AM::operator_type g) {
// 1. Value Monoid
typename AM::value_type;
{ AM::id() } -> std::same_as<typename AM::value_type>;
{ AM::op(a, b) } -> std::same_as<typename AM::value_type>;
// 2. Operator Monoid
typename AM::operator_type;
{ AM::op_id() } -> std::same_as<typename AM::operator_type>;
{ AM::op_comp(f, g) } -> std::same_as<typename AM::operator_type>; // Composition order: f(g(x))
// 3. Mapping: Operator x Value -> Value
{ AM::mapping(f, a) } -> std::same_as<typename AM::value_type>;
};
// Concept for acted monoids whose value monoid is a commutative group.
// The value operation must obey commutativity and inverse laws.
template <typename AM>
concept IsCommutativeActedGroup = IsActedMonoid<AM> && requires(typename AM::value_type a) {
{ AM::inv(a) } -> std::same_as<typename AM::value_type>;
};
} // namespace acted_monoid
} // namespace m1une
#line 1 "ds/detail/rollback_journal.hpp"
#line 8 "ds/detail/rollback_journal.hpp"
#include <limits>
#line 11 "ds/detail/rollback_journal.hpp"
namespace m1une {
namespace ds {
namespace detail {
template <class Node>
struct RollbackJournal {
struct Change {
int index;
Node value;
};
struct Checkpoint {
std::size_t change_size;
std::size_t node_size;
std::uint64_t epoch;
};
std::vector<Node> nodes;
std::vector<Change> changes;
std::vector<Checkpoint> checkpoints;
std::vector<std::uint64_t> saved_epoch;
std::uint64_t next_epoch = 1;
std::uint64_t new_epoch() {
if (next_epoch == 0) {
std::fill(saved_epoch.begin(), saved_epoch.end(), 0);
next_epoch = 1;
}
return next_epoch++;
}
int size() const { return int(nodes.size()); }
Node& operator[](int index) { return nodes[index]; }
const Node& operator[](int index) const { return nodes[index]; }
template <class... Args>
int emplace(Args&&... args) {
assert(nodes.size() < std::size_t(std::numeric_limits<int>::max()));
int index = int(nodes.size());
nodes.emplace_back(std::forward<Args>(args)...);
saved_epoch.push_back(0);
return index;
}
int snapshot() {
assert(checkpoints.size() < std::size_t(std::numeric_limits<int>::max()));
checkpoints.push_back(Checkpoint{changes.size(), nodes.size(), new_epoch()});
return int(checkpoints.size());
}
void touch(int index) {
assert(0 <= index && index < size());
if (checkpoints.empty()) return;
const Checkpoint& checkpoint = checkpoints.back();
if (std::size_t(index) >= checkpoint.node_size) return;
if (saved_epoch[index] == checkpoint.epoch) return;
saved_epoch[index] = checkpoint.epoch;
changes.push_back(Change{index, nodes[index]});
}
int snapshot_count() const { return int(checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
checkpoints.reserve(count);
}
void reserve_changes(std::size_t count) { changes.reserve(count); }
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
Checkpoint checkpoint = checkpoints[state - 1];
while (changes.size() > checkpoint.change_size) {
Change change = std::move(changes.back());
changes.pop_back();
nodes[change.index] = std::move(change.value);
}
nodes.erase(nodes.begin() + checkpoint.node_size, nodes.end());
saved_epoch.resize(checkpoint.node_size);
checkpoints.resize(state);
checkpoints.back().change_size = changes.size();
checkpoints.back().node_size = nodes.size();
checkpoints.back().epoch = new_epoch();
}
void clear_history() {
changes.clear();
checkpoints.clear();
std::fill(saved_epoch.begin(), saved_epoch.end(), 0);
}
void clear() {
nodes.clear();
changes.clear();
checkpoints.clear();
saved_epoch.clear();
next_epoch = 1;
}
};
} // namespace detail
} // namespace ds
} // namespace m1une
#line 15 "ds/dynamic_array/rollback_dynamic_lazy_monoid_array.hpp"
namespace m1une {
namespace ds {
template <m1une::acted_monoid::IsActedMonoid ActedMonoid>
struct RollbackDynamicLazyMonoidArray {
using T = typename ActedMonoid::value_type;
using F = typename ActedMonoid::operator_type;
private:
static constexpr bool value_commutative = [] {
if constexpr (requires { ActedMonoid::commutative; }) {
return bool(ActedMonoid::commutative);
} else {
return false;
}
}();
struct EmptyReverseProduct {};
using ReverseProduct = std::conditional_t<value_commutative, EmptyReverseProduct, T>;
static constexpr bool count_stored_in_value = requires(const T& value) {
{ ActedMonoid::size(value) } -> std::convertible_to<int>;
};
struct EmptyCount {};
using Count = std::conditional_t<count_stored_in_value, EmptyCount, int>;
static ReverseProduct make_reverse_product(const T& value) {
if constexpr (value_commutative) {
return {};
} else {
return value;
}
}
static Count make_count(int count) {
if constexpr (count_stored_in_value) {
return {};
} else {
return count;
}
}
struct Node {
T val;
T prod;
[[no_unique_address]] ReverseProduct rprod;
F lazy;
std::uint32_t priority : 30;
std::uint32_t rev : 1;
std::uint32_t has_lazy : 1;
[[no_unique_address]] Count count;
int l, r;
Node()
: val(ActedMonoid::id()),
prod(ActedMonoid::id()),
rprod(make_reverse_product(prod)),
lazy(ActedMonoid::op_id()),
priority(0),
rev(false),
has_lazy(false),
count(make_count(0)),
l(0),
r(0) {}
Node(T value, int node_priority)
: val(std::move(value)),
prod(val),
rprod(make_reverse_product(val)),
lazy(ActedMonoid::op_id()),
priority(std::uint32_t(node_priority)),
rev(false),
has_lazy(false),
count(make_count(1)),
l(0),
r(0) {}
};
detail::RollbackJournal<Node> _journal;
struct StateCheckpoint { int root; int free_head; };
std::vector<StateCheckpoint> _state_checkpoints;
int root;
int free_head;
std::uint32_t rng_state;
int node_count(int t) const {
if constexpr (count_stored_in_value) {
return int(ActedMonoid::size(_journal[t].prod));
} else {
return _journal[t].count;
}
}
void set_node_count(int t, int count) {
_journal.touch(t);
if constexpr (!count_stored_in_value) {
_journal[t].count = count;
}
}
template <typename U>
static T make_value(const U& value) {
if constexpr (requires(U x) { ActedMonoid::make(x); }) {
return ActedMonoid::make(value);
} else {
return static_cast<T>(value);
}
}
static T mapping_at(const F& f, const T& value, long long ord) {
if constexpr (requires(F g, T x, long long i) { ActedMonoid::mapping(g, x, i); }) {
return ActedMonoid::mapping(f, value, ord);
} else {
return ActedMonoid::mapping(f, value);
}
}
static F shift_operator(const F& f, long long ord) {
if constexpr (requires(F g, long long i) { ActedMonoid::op_shift(g, i); }) {
return ActedMonoid::op_shift(f, ord);
} else {
return f;
}
}
static F reverse_operator(const F& f, long long size) {
if constexpr (requires(F g, long long n) { ActedMonoid::op_reverse(g, n); }) {
return ActedMonoid::op_reverse(f, size);
} else {
return f;
}
}
int new_node(T value) {
int priority = next_priority();
if (free_head) {
int res = free_head;
_journal.touch(res);
free_head = _journal[res].l;
_journal[res] = Node(std::move(value), priority);
return res;
}
_journal.emplace(std::move(value), priority);
return int(_journal.nodes.size()) - 1;
}
void release_node(int t) {
_journal.touch(t);
_journal[t].l = free_head;
free_head = t;
}
int next_priority() {
rng_state ^= rng_state << 13;
rng_state ^= rng_state >> 17;
rng_state ^= rng_state << 5;
return int(rng_state);
}
void update(int t) {
if (!t) return;
_journal.touch(t);
int l = _journal[t].l;
int r = _journal[t].r;
set_node_count(t, 1 + node_count(l) + node_count(r));
_journal[t].prod = ActedMonoid::op(ActedMonoid::op(_journal[l].prod, _journal[t].val), _journal[r].prod);
if constexpr (!value_commutative) {
_journal[t].rprod = ActedMonoid::op(ActedMonoid::op(_journal[r].rprod, _journal[t].val), _journal[l].rprod);
}
}
void all_apply(int t, const F& f) {
if (!t) return;
_journal.touch(t);
int left_count = node_count(_journal[t].l);
_journal[t].val = mapping_at(f, _journal[t].val, left_count);
_journal[t].prod = mapping_at(f, _journal[t].prod, 0);
if constexpr (!value_commutative) {
_journal[t].rprod = mapping_at(reverse_operator(f, node_count(t)), _journal[t].rprod, 0);
}
_journal[t].lazy = ActedMonoid::op_comp(f, _journal[t].lazy);
_journal[t].has_lazy = true;
}
void apply_reverse(int t) {
if (!t) return;
_journal.touch(t);
std::swap(_journal[t].l, _journal[t].r);
_journal[t].rev = !_journal[t].rev;
if constexpr (!value_commutative) {
std::swap(_journal[t].prod, _journal[t].rprod);
}
if (_journal[t].has_lazy) {
_journal[t].lazy = reverse_operator(_journal[t].lazy, node_count(t));
}
}
void push(int t) {
if (!t) return;
_journal.touch(t);
if (_journal[t].rev) {
apply_reverse(_journal[t].l);
apply_reverse(_journal[t].r);
_journal[t].rev = false;
}
if (_journal[t].has_lazy) {
all_apply(_journal[t].l, _journal[t].lazy);
all_apply(_journal[t].r, shift_operator(_journal[t].lazy, node_count(_journal[t].l) + 1));
_journal[t].lazy = ActedMonoid::op_id();
_journal[t].has_lazy = false;
}
}
void split(int t, int pos, int& l, int& r) {
if (!t) {
l = r = 0;
return;
}
if (pos == 0) {
l = 0;
r = t;
return;
}
if (pos == node_count(t)) {
l = t;
r = 0;
return;
}
_journal.touch(t);
push(t);
int left_count = node_count(_journal[t].l);
if (pos == left_count) {
l = _journal[t].l;
_journal[t].l = 0;
update(t);
r = t;
return;
}
if (pos == left_count + 1) {
r = _journal[t].r;
_journal[t].r = 0;
update(t);
l = t;
return;
}
if (pos <= left_count) {
split(_journal[t].l, pos, l, _journal[t].l);
r = t;
} else {
split(_journal[t].r, pos - left_count - 1, _journal[t].r, r);
l = t;
}
update(t);
}
int merge(int l, int r) {
if (!l || !r) return l ? l : r;
if (_journal[l].priority > _journal[r].priority) {
push(l);
_journal.touch(l);
if (_journal[l].r) {
_journal[l].r = merge(_journal[l].r, r);
} else {
_journal[l].r = r;
}
update(l);
return l;
} else {
push(r);
_journal.touch(r);
if (_journal[r].l) {
_journal[r].l = merge(l, _journal[r].l);
} else {
_journal[r].l = l;
}
update(r);
return r;
}
}
void split_three(int t, int ql, int qr, int& a, int& b, int& c) {
if (ql == qr) {
split(t, ql, a, c);
b = 0;
return;
}
if (ql == 0 && qr == node_count(t)) {
a = c = 0;
b = t;
return;
}
_journal.touch(t);
push(t);
int left_count = node_count(_journal[t].l);
if (qr <= left_count) {
split_three(_journal[t].l, ql, qr, a, b, _journal[t].l);
c = t;
update(t);
} else if (left_count < ql) {
split_three(_journal[t].r, ql - left_count - 1, qr - left_count - 1, _journal[t].r, b, c);
a = t;
update(t);
} else {
split(_journal[t].l, ql, a, _journal[t].l);
split(_journal[t].r, qr - left_count - 1, _journal[t].r, c);
b = t;
update(t);
}
}
int merge_three(int a, int b, int c) {
if (!a) return merge(b, c);
if (!b) return merge(a, c);
if (!c) return merge(a, b);
std::uint32_t pa = _journal[a].priority;
std::uint32_t pb = _journal[b].priority;
std::uint32_t pc = _journal[c].priority;
if (pb >= pa && pb >= pc) {
push(b);
_journal.touch(b);
_journal[b].l = merge(a, _journal[b].l);
_journal[b].r = merge(_journal[b].r, c);
update(b);
return b;
}
if (pa >= pc) {
push(a);
_journal.touch(a);
_journal[a].r = merge_three(_journal[a].r, b, c);
update(a);
return a;
}
push(c);
_journal.touch(c);
_journal[c].l = merge_three(a, b, _journal[c].l);
update(c);
return c;
}
int insert_node(int t, int pos, int node) {
if (!t) return node;
if (_journal[node].priority > _journal[t].priority) {
_journal.touch(node);
split(t, pos, _journal[node].l, _journal[node].r);
update(node);
return node;
}
push(t);
_journal.touch(t);
int left_count = node_count(_journal[t].l);
if (pos <= left_count) {
_journal[t].l = insert_node(_journal[t].l, pos, node);
} else {
_journal[t].r = insert_node(_journal[t].r, pos - left_count - 1, node);
}
update(t);
return t;
}
int erase_node(int t, int pos) {
push(t);
_journal.touch(t);
int left_count = node_count(_journal[t].l);
if (pos < left_count) {
_journal[t].l = erase_node(_journal[t].l, pos);
update(t);
return t;
}
if (pos == left_count) {
int res = merge(_journal[t].l, _journal[t].r);
release_node(t);
return res;
}
_journal[t].r = erase_node(_journal[t].r, pos - left_count - 1);
update(t);
return t;
}
void set_node(int t, int pos, T value) {
push(t);
_journal.touch(t);
int left_count = node_count(_journal[t].l);
if (pos < left_count) {
set_node(_journal[t].l, pos, std::move(value));
} else if (pos == left_count) {
_journal[t].val = std::move(value);
} else {
set_node(_journal[t].r, pos - left_count - 1, std::move(value));
}
update(t);
}
void apply_node(int t, int pos, const F& f) {
push(t);
_journal.touch(t);
int left_count = node_count(_journal[t].l);
if (pos < left_count) {
apply_node(_journal[t].l, pos, f);
} else if (pos == left_count) {
_journal[t].val = mapping_at(f, _journal[t].val, 0);
} else {
apply_node(_journal[t].r, pos - left_count - 1, f);
}
update(t);
}
void apply_range(int t, int ql, int qr, const F& f) {
if (ql == 0 && qr == node_count(t)) {
all_apply(t, f);
return;
}
push(t);
_journal.touch(t);
int left_count = node_count(_journal[t].l);
if (qr <= left_count) {
apply_range(_journal[t].l, ql, qr, f);
} else if (left_count < ql) {
apply_range(_journal[t].r, ql - left_count - 1, qr - left_count - 1, f);
} else {
if (ql < left_count) {
apply_range(_journal[t].l, ql, left_count, f);
}
_journal[t].val = mapping_at(f, _journal[t].val, left_count - ql);
if (left_count + 1 < qr) {
apply_range(_journal[t].r, 0, qr - left_count - 1,
shift_operator(f, left_count + 1 - ql));
}
}
update(t);
}
T prod_range(int t, int ql, int qr) {
if (ql == 0 && qr == node_count(t)) return _journal[t].prod;
push(t);
int left_count = node_count(_journal[t].l);
if (qr <= left_count) {
return prod_range(_journal[t].l, ql, qr);
}
if (left_count < ql) {
return prod_range(_journal[t].r, ql - left_count - 1, qr - left_count - 1);
}
T res = _journal[t].val;
if (ql < left_count) {
res = ActedMonoid::op(prod_range(_journal[t].l, ql, left_count), res);
}
if (left_count + 1 < qr) {
res = ActedMonoid::op(res, prod_range(_journal[t].r, 0, qr - left_count - 1));
}
return res;
}
int find_node(int t, int pos) {
while (t) {
push(t);
int left_count = node_count(_journal[t].l);
if (pos < left_count) {
t = _journal[t].l;
} else if (pos == left_count) {
return t;
} else {
pos -= left_count + 1;
t = _journal[t].r;
}
}
return 0;
}
void dump_dfs(int t, std::vector<T>& res) {
if (!t) return;
push(t);
dump_dfs(_journal[t].l, res);
res.push_back(_journal[t].val);
dump_dfs(_journal[t].r, res);
update(t);
}
void dump_range_dfs(int t, int ql, int qr, int offset, std::vector<T>& res) {
if (!t || qr <= offset || offset + node_count(t) <= ql) return;
push(t);
int left_count = node_count(_journal[t].l);
int node_pos = offset + left_count;
dump_range_dfs(_journal[t].l, ql, qr, offset, res);
if (ql <= node_pos && node_pos < qr) {
res.push_back(_journal[t].val);
}
dump_range_dfs(_journal[t].r, ql, qr, node_pos + 1, res);
update(t);
}
int clone_subtree_from(const RollbackDynamicLazyMonoidArray& other, int t) {
if (!t) return 0;
Node source = other._journal[t];
int res = int(_journal.nodes.size());
_journal.emplace(std::move(source));
_journal[res].l = clone_subtree_from(other, other._journal[t].l);
_journal[res].r = clone_subtree_from(other, other._journal[t].r);
return res;
}
void update_dfs(int t) {
if (!t) return;
update_dfs(_journal[t].l);
update_dfs(_journal[t].r);
update(t);
}
int build_cartesian(int first, int last) {
if (first == last) return 0;
std::vector<int> stack;
stack.reserve(last - first);
for (int i = first; i < last; i++) {
int left_child = 0;
while (!stack.empty() && _journal[stack.back()].priority < _journal[i].priority) {
left_child = stack.back();
stack.pop_back();
}
_journal[i].l = left_child;
if (!stack.empty()) {
_journal[stack.back()].r = i;
}
stack.push_back(i);
}
int res = stack.front();
update_dfs(res);
return res;
}
int build_from_vector(const std::vector<T>& v) {
int saved_free_head = std::exchange(free_head, 0);
int first = int(_journal.nodes.size());
_journal.nodes.reserve(_journal.nodes.size() + v.size());
for (const T& x : v) {
new_node(x);
}
int result = build_cartesian(first, int(_journal.nodes.size()));
free_head = saved_free_head;
return result;
}
int build_from_vector(std::vector<T>&& v) {
int saved_free_head = std::exchange(free_head, 0);
int first = int(_journal.nodes.size());
_journal.nodes.reserve(_journal.nodes.size() + v.size());
for (T& x : v) {
new_node(std::move(x));
}
int result = build_cartesian(first, int(_journal.nodes.size()));
free_head = saved_free_head;
return result;
}
template <typename U>
int build_from_values(const std::vector<U>& v) {
int saved_free_head = std::exchange(free_head, 0);
int first = int(_journal.nodes.size());
_journal.nodes.reserve(_journal.nodes.size() + v.size());
for (const U& x : v) {
new_node(make_value(x));
}
int result = build_cartesian(first, int(_journal.nodes.size()));
free_head = saved_free_head;
return result;
}
void release_subtree(int t) {
if (!t) return;
std::vector<int> stack(1, t);
while (!stack.empty()) {
int node = stack.back();
stack.pop_back();
int left = _journal[node].l;
int right = _journal[node].r;
if (left) stack.push_back(left);
if (right) stack.push_back(right);
release_node(node);
}
}
void reset_to_empty() {
_journal.clear();
_journal.emplace();
root = 0;
_state_checkpoints.clear();
free_head = 0;
}
public:
RollbackDynamicLazyMonoidArray()
: root(0),
free_head(0),
rng_state(std::uint32_t(std::chrono::steady_clock::now().time_since_epoch().count())) {
_journal.emplace();
if (rng_state == 0) rng_state = 1;
}
RollbackDynamicLazyMonoidArray(const RollbackDynamicLazyMonoidArray& other)
: root(other.root), free_head(other.free_head), rng_state(other.rng_state) {
_journal.nodes = other._journal.nodes;
_journal.saved_epoch.assign(_journal.nodes.size(), 0);
}
RollbackDynamicLazyMonoidArray(RollbackDynamicLazyMonoidArray&& other) noexcept
: _journal(std::move(other._journal)),
_state_checkpoints(std::move(other._state_checkpoints)),
root(other.root),
free_head(other.free_head),
rng_state(other.rng_state) {
other.reset_to_empty();
}
RollbackDynamicLazyMonoidArray& operator=(const RollbackDynamicLazyMonoidArray& other) {
if (this != &other) {
_journal.nodes = other._journal.nodes;
_journal.saved_epoch.assign(_journal.nodes.size(), 0);
_journal.changes.clear();
_journal.checkpoints.clear();
_state_checkpoints.clear();
root = other.root;
free_head = other.free_head;
rng_state = other.rng_state;
}
return *this;
}
RollbackDynamicLazyMonoidArray& operator=(RollbackDynamicLazyMonoidArray&& other) noexcept {
if (this != &other) {
_journal = std::move(other._journal);
_state_checkpoints = std::move(other._state_checkpoints);
root = other.root;
free_head = other.free_head;
rng_state = other.rng_state;
other.reset_to_empty();
}
return *this;
}
explicit RollbackDynamicLazyMonoidArray(int n)
: RollbackDynamicLazyMonoidArray(n, ActedMonoid::id()) {}
RollbackDynamicLazyMonoidArray(int n, const T& value) : RollbackDynamicLazyMonoidArray() {
assert(0 <= n);
_journal.nodes.reserve(n + 1);
int first = int(_journal.nodes.size());
for (int i = 0; i < n; i++) {
new_node(value);
}
root = build_cartesian(first, int(_journal.nodes.size()));
}
explicit RollbackDynamicLazyMonoidArray(const std::vector<T>& v) : RollbackDynamicLazyMonoidArray() {
_journal.nodes.reserve(v.size() + 1);
root = build_from_vector(v);
}
explicit RollbackDynamicLazyMonoidArray(std::vector<T>&& v) : RollbackDynamicLazyMonoidArray() {
_journal.nodes.reserve(v.size() + 1);
root = build_from_vector(std::move(v));
}
template <typename U>
requires(!std::same_as<U, T>) && (requires(U x) { ActedMonoid::make(x); } || std::convertible_to<U, T>)
explicit RollbackDynamicLazyMonoidArray(const std::vector<U>& v) : RollbackDynamicLazyMonoidArray() {
_journal.nodes.reserve(v.size() + 1);
root = build_from_values(v);
}
RollbackDynamicLazyMonoidArray(std::initializer_list<T> init) : RollbackDynamicLazyMonoidArray() {
_journal.nodes.reserve(init.size() + 1);
for (const T& x : init) push_back(x);
}
int size() const {
return node_count(root);
}
std::size_t node_count() const { return _journal.nodes.size() - 1; }
void reserve(std::size_t capacity) {
_journal.nodes.reserve(capacity + 1);
_journal.saved_epoch.reserve(capacity + 1);
}
bool empty() const {
return size() == 0;
}
void clear() {
release_subtree(root);
root = 0;
}
void insert(int pos, T value) {
assert(0 <= pos && pos <= size());
root = insert_node(root, pos, new_node(std::move(value)));
}
void insert(int pos, const std::vector<T>& v) {
assert(0 <= pos && pos <= size());
_journal.nodes.reserve(_journal.nodes.size() + v.size());
int mid = build_from_vector(v);
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void insert(int pos, std::vector<T>&& v) {
assert(0 <= pos && pos <= size());
_journal.nodes.reserve(_journal.nodes.size() + v.size());
int mid = build_from_vector(std::move(v));
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void insert(int pos, std::initializer_list<T> init) {
insert(pos, std::vector<T>(init));
}
void insert(int pos, const RollbackDynamicLazyMonoidArray& other) {
assert(0 <= pos && pos <= size());
if (other.empty()) return;
_journal.nodes.reserve(_journal.nodes.size() + other.size());
int mid = clone_subtree_from(other, other.root);
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void push_back(T value) {
insert(size(), std::move(value));
}
void push_front(T value) {
insert(0, std::move(value));
}
void append(const std::vector<T>& v) {
insert(size(), v);
}
void append(std::vector<T>&& v) {
insert(size(), std::move(v));
}
void append(const RollbackDynamicLazyMonoidArray& other) {
insert(size(), other);
}
void erase(int pos) {
assert(0 <= pos && pos < size());
root = erase_node(root, pos);
}
void erase(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return;
int a, b, c;
split_three(root, l, r, a, b, c);
release_subtree(b);
root = merge(a, c);
}
void pop_back() {
assert(!empty());
erase(size() - 1);
}
void pop_front() {
assert(!empty());
erase(0);
}
T get(int pos) {
assert(0 <= pos && pos < size());
int t = find_node(root, pos);
return _journal[t].val;
}
T operator[](int pos) {
return get(pos);
}
T front() {
assert(!empty());
return get(0);
}
T back() {
assert(!empty());
return get(size() - 1);
}
void set(int pos, T value) {
assert(0 <= pos && pos < size());
set_node(root, pos, std::move(value));
}
void reverse(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return;
int a, b, c;
split_three(root, l, r, a, b, c);
apply_reverse(b);
root = merge_three(a, b, c);
}
void reverse() {
apply_reverse(root);
}
void rotate(int l, int m, int r) {
assert(0 <= l && l <= m && m <= r && r <= size());
if (l == m || m == r) return;
int a, b, c, d;
split(root, l, a, b);
split(b, m - l, b, c);
split(c, r - m, c, d);
root = merge(merge(a, c), merge(b, d));
}
void apply(int pos, const F& f) {
assert(0 <= pos && pos < size());
apply_node(root, pos, f);
}
void apply(int l, int r, const F& f) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return;
apply_range(root, l, r, f);
}
T prod(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return ActedMonoid::id();
return prod_range(root, l, r);
}
T all_prod() const {
return _journal[root].prod;
}
std::vector<T> to_vector() {
std::vector<T> res;
res.reserve(size());
dump_dfs(root, res);
return res;
}
std::vector<T> to_vector(int l, int r) {
assert(0 <= l && l <= r && r <= size());
std::vector<T> res;
res.reserve(r - l);
dump_range_dfs(root, l, r, 0, res);
return res;
}
RollbackDynamicLazyMonoidArray split_off(int pos) {
assert(0 <= pos && pos <= size());
int l, r;
split(root, pos, l, r);
root = l;
RollbackDynamicLazyMonoidArray res;
res._journal.nodes.reserve(node_count(r) + 1);
res.root = res.clone_subtree_from(*this, r);
release_subtree(r);
return res;
}
void set_inplace(int pos, T value) { set(pos, std::move(value)); }
void apply_inplace(int pos, const F& f) { apply(pos, f); }
void apply_inplace(int left, int right, const F& f) { apply(left, right, f); }
int snapshot() {
int state = _journal.snapshot();
_state_checkpoints.push_back(StateCheckpoint{root, free_head});
assert(state == int(_state_checkpoints.size()));
return state;
}
int snapshot_count() const { return int(_state_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_journal.reserve_snapshots(count);
_state_checkpoints.reserve(count);
}
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
StateCheckpoint checkpoint = _state_checkpoints[state - 1];
_journal.rollback(state);
root = checkpoint.root;
free_head = checkpoint.free_head;
_state_checkpoints.resize(state);
}
void clear_history() {
_journal.clear_history();
_state_checkpoints.clear();
}
void release() { reset_to_empty(); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/dynamic_array/rollback_dynamic_monoid_array.hpp"
#line 10 "ds/dynamic_array/rollback_dynamic_monoid_array.hpp"
#line 1 "ds/dynamic_array/dynamic_monoid_array.hpp"
#line 11 "ds/dynamic_array/dynamic_monoid_array.hpp"
#line 13 "ds/dynamic_array/dynamic_monoid_array.hpp"
namespace m1une {
namespace ds {
template <m1une::monoid::IsMonoid Monoid>
struct DynamicMonoidArray {
using T = typename Monoid::value_type;
private:
struct Node {
T val;
T prod;
T rprod;
int priority;
int count;
int l, r;
bool rev;
Node()
: val(Monoid::id()),
prod(Monoid::id()),
rprod(Monoid::id()),
priority(0),
count(0),
l(0),
r(0),
rev(false) {}
Node(T value, int node_priority)
: val(std::move(value)), prod(val), rprod(val), priority(node_priority), count(1), l(0), r(0), rev(false) {}
};
std::vector<Node> pool;
int root;
std::uint32_t rng_state;
template <typename U>
static T make_value(const U& value) {
if constexpr (requires(U x) { Monoid::make(x); }) {
return Monoid::make(value);
} else {
return static_cast<T>(value);
}
}
int new_node(T value) {
pool.push_back(Node(std::move(value), next_priority()));
return int(pool.size()) - 1;
}
int next_priority() {
rng_state ^= rng_state << 13;
rng_state ^= rng_state >> 17;
rng_state ^= rng_state << 5;
return int(rng_state);
}
void update(int t) {
if (!t) return;
int l = pool[t].l;
int r = pool[t].r;
pool[t].count = 1 + pool[l].count + pool[r].count;
pool[t].prod = Monoid::op(Monoid::op(pool[l].prod, pool[t].val), pool[r].prod);
pool[t].rprod = Monoid::op(Monoid::op(pool[r].rprod, pool[t].val), pool[l].rprod);
}
void apply_reverse(int t) {
if (!t) return;
pool[t].rev = !pool[t].rev;
std::swap(pool[t].prod, pool[t].rprod);
}
void push(int t) {
if (!t || !pool[t].rev) return;
std::swap(pool[t].l, pool[t].r);
apply_reverse(pool[t].l);
apply_reverse(pool[t].r);
pool[t].rev = false;
}
void split(int t, int pos, int& l, int& r) {
if (!t) {
l = r = 0;
return;
}
if (pos == 0) {
l = 0;
r = t;
return;
}
if (pos == pool[t].count) {
l = t;
r = 0;
return;
}
push(t);
int left_count = pool[pool[t].l].count;
if (pos == left_count) {
l = pool[t].l;
pool[t].l = 0;
update(t);
r = t;
return;
}
if (pos == left_count + 1) {
r = pool[t].r;
pool[t].r = 0;
update(t);
l = t;
return;
}
if (pos <= left_count) {
split(pool[t].l, pos, l, pool[t].l);
r = t;
} else {
split(pool[t].r, pos - left_count - 1, pool[t].r, r);
l = t;
}
update(t);
}
int merge(int l, int r) {
if (!l || !r) return l ? l : r;
if (pool[l].priority > pool[r].priority) {
push(l);
if (pool[l].r) {
pool[l].r = merge(pool[l].r, r);
} else {
pool[l].r = r;
}
update(l);
return l;
} else {
push(r);
if (pool[r].l) {
pool[r].l = merge(l, pool[r].l);
} else {
pool[r].l = l;
}
update(r);
return r;
}
}
int insert_node(int t, int pos, int node) {
if (!t) return node;
if (pool[node].priority > pool[t].priority) {
split(t, pos, pool[node].l, pool[node].r);
update(node);
return node;
}
push(t);
int left_count = pool[pool[t].l].count;
if (pos <= left_count) {
pool[t].l = insert_node(pool[t].l, pos, node);
} else {
pool[t].r = insert_node(pool[t].r, pos - left_count - 1, node);
}
update(t);
return t;
}
int erase_node(int t, int pos) {
push(t);
int left_count = pool[pool[t].l].count;
if (pos < left_count) {
pool[t].l = erase_node(pool[t].l, pos);
update(t);
return t;
}
if (pos == left_count) {
return merge(pool[t].l, pool[t].r);
}
pool[t].r = erase_node(pool[t].r, pos - left_count - 1);
update(t);
return t;
}
void set_node(int t, int pos, T value) {
push(t);
int left_count = pool[pool[t].l].count;
if (pos < left_count) {
set_node(pool[t].l, pos, std::move(value));
} else if (pos == left_count) {
pool[t].val = std::move(value);
} else {
set_node(pool[t].r, pos - left_count - 1, std::move(value));
}
update(t);
}
int find_node(int t, int pos) {
while (t) {
push(t);
int left_count = pool[pool[t].l].count;
if (pos < left_count) {
t = pool[t].l;
} else if (pos == left_count) {
return t;
} else {
pos -= left_count + 1;
t = pool[t].r;
}
}
return 0;
}
int find_node(int t, int pos, bool reversed) const {
while (t) {
bool cur_reversed = reversed ^ pool[t].rev;
int l = cur_reversed ? pool[t].r : pool[t].l;
int r = cur_reversed ? pool[t].l : pool[t].r;
int left_count = pool[l].count;
if (pos < left_count) {
t = l;
reversed = cur_reversed;
} else if (pos == left_count) {
return t;
} else {
pos -= left_count + 1;
t = r;
reversed = cur_reversed;
}
}
return 0;
}
void dump_dfs(int t, std::vector<T>& res, bool reversed = false) const {
if (!t) return;
bool cur_reversed = reversed ^ pool[t].rev;
int l = cur_reversed ? pool[t].r : pool[t].l;
int r = cur_reversed ? pool[t].l : pool[t].r;
dump_dfs(l, res, cur_reversed);
res.push_back(pool[t].val);
dump_dfs(r, res, cur_reversed);
}
void dump_range_dfs(int t, int ql, int qr, int offset, std::vector<T>& res, bool reversed = false) const {
if (!t || qr <= offset || offset + pool[t].count <= ql) return;
bool cur_reversed = reversed ^ pool[t].rev;
int l = cur_reversed ? pool[t].r : pool[t].l;
int r = cur_reversed ? pool[t].l : pool[t].r;
int left_count = pool[l].count;
int node_pos = offset + left_count;
dump_range_dfs(l, ql, qr, offset, res, cur_reversed);
if (ql <= node_pos && node_pos < qr) {
res.push_back(pool[t].val);
}
dump_range_dfs(r, ql, qr, node_pos + 1, res, cur_reversed);
}
int clone_subtree_from(const DynamicMonoidArray& other, int t) {
if (!t) return 0;
int res = int(pool.size());
pool.push_back(other.pool[t]);
pool[res].l = clone_subtree_from(other, other.pool[t].l);
pool[res].r = clone_subtree_from(other, other.pool[t].r);
return res;
}
void update_dfs(int t) {
if (!t) return;
update_dfs(pool[t].l);
update_dfs(pool[t].r);
update(t);
}
int build_cartesian(int first, int last) {
if (first == last) return 0;
std::vector<int> stack;
stack.reserve(last - first);
for (int i = first; i < last; i++) {
int left_child = 0;
while (!stack.empty() && pool[stack.back()].priority < pool[i].priority) {
left_child = stack.back();
stack.pop_back();
}
pool[i].l = left_child;
if (!stack.empty()) {
pool[stack.back()].r = i;
}
stack.push_back(i);
}
int res = stack.front();
update_dfs(res);
return res;
}
int build_from_vector(const std::vector<T>& v) {
int first = int(pool.size());
pool.reserve(pool.size() + v.size());
for (const T& x : v) {
new_node(x);
}
return build_cartesian(first, int(pool.size()));
}
int build_from_vector(std::vector<T>&& v) {
int first = int(pool.size());
pool.reserve(pool.size() + v.size());
for (T& x : v) {
new_node(std::move(x));
}
return build_cartesian(first, int(pool.size()));
}
template <typename U>
int build_from_values(const std::vector<U>& v) {
int first = int(pool.size());
pool.reserve(pool.size() + v.size());
for (const U& x : v) {
new_node(make_value(x));
}
return build_cartesian(first, int(pool.size()));
}
void reset_to_empty() {
pool.clear();
pool.push_back(Node());
root = 0;
}
public:
DynamicMonoidArray()
: root(0), rng_state(std::uint32_t(std::chrono::steady_clock::now().time_since_epoch().count())) {
pool.push_back(Node());
if (rng_state == 0) rng_state = 1;
}
DynamicMonoidArray(const DynamicMonoidArray& other)
: pool(other.pool), root(other.root), rng_state(other.rng_state) {}
DynamicMonoidArray(DynamicMonoidArray&& other) noexcept
: pool(std::move(other.pool)), root(other.root), rng_state(other.rng_state) {
other.reset_to_empty();
}
DynamicMonoidArray& operator=(const DynamicMonoidArray& other) {
if (this != &other) {
pool = other.pool;
root = other.root;
rng_state = other.rng_state;
}
return *this;
}
DynamicMonoidArray& operator=(DynamicMonoidArray&& other) noexcept {
if (this != &other) {
pool = std::move(other.pool);
root = other.root;
rng_state = other.rng_state;
other.reset_to_empty();
}
return *this;
}
explicit DynamicMonoidArray(int n) : DynamicMonoidArray(n, Monoid::id()) {}
DynamicMonoidArray(int n, const T& value) : DynamicMonoidArray() {
assert(0 <= n);
pool.reserve(n + 1);
int first = int(pool.size());
for (int i = 0; i < n; i++) {
new_node(value);
}
root = build_cartesian(first, int(pool.size()));
}
explicit DynamicMonoidArray(const std::vector<T>& v) : DynamicMonoidArray() {
pool.reserve(v.size() + 1);
root = build_from_vector(v);
}
explicit DynamicMonoidArray(std::vector<T>&& v) : DynamicMonoidArray() {
pool.reserve(v.size() + 1);
root = build_from_vector(std::move(v));
}
template <typename U>
requires(!std::same_as<U, T>) && (requires(U x) { Monoid::make(x); } || std::convertible_to<U, T>)
explicit DynamicMonoidArray(const std::vector<U>& v) : DynamicMonoidArray() {
pool.reserve(v.size() + 1);
root = build_from_values(v);
}
DynamicMonoidArray(std::initializer_list<T> init) : DynamicMonoidArray() {
pool.reserve(init.size() + 1);
for (const T& x : init) push_back(x);
}
int size() const {
return pool[root].count;
}
bool empty() const {
return size() == 0;
}
void clear() {
reset_to_empty();
}
void insert(int pos, T value) {
assert(0 <= pos && pos <= size());
root = insert_node(root, pos, new_node(std::move(value)));
}
void insert(int pos, const std::vector<T>& v) {
assert(0 <= pos && pos <= size());
pool.reserve(pool.size() + v.size());
int mid = build_from_vector(v);
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void insert(int pos, std::vector<T>&& v) {
assert(0 <= pos && pos <= size());
pool.reserve(pool.size() + v.size());
int mid = build_from_vector(std::move(v));
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void insert(int pos, std::initializer_list<T> init) {
insert(pos, std::vector<T>(init));
}
void insert(int pos, const DynamicMonoidArray& other) {
assert(0 <= pos && pos <= size());
if (other.empty()) return;
pool.reserve(pool.size() + other.size());
int mid = clone_subtree_from(other, other.root);
int l, r;
split(root, pos, l, r);
root = merge(merge(l, mid), r);
}
void push_back(T value) {
insert(size(), std::move(value));
}
void push_front(T value) {
insert(0, std::move(value));
}
void append(const std::vector<T>& v) {
insert(size(), v);
}
void append(std::vector<T>&& v) {
insert(size(), std::move(v));
}
void append(const DynamicMonoidArray& other) {
insert(size(), other);
}
void erase(int pos) {
assert(0 <= pos && pos < size());
root = erase_node(root, pos);
}
void erase(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return;
int a, b, c;
split(root, l, a, b);
split(b, r - l, b, c);
root = merge(a, c);
}
void pop_back() {
assert(!empty());
erase(size() - 1);
}
void pop_front() {
assert(!empty());
erase(0);
}
T get(int pos) const {
assert(0 <= pos && pos < size());
return pool[find_node(root, pos, false)].val;
}
T operator[](int pos) const {
return get(pos);
}
T front() const {
assert(!empty());
return get(0);
}
T back() const {
assert(!empty());
return get(size() - 1);
}
void set(int pos, T value) {
assert(0 <= pos && pos < size());
set_node(root, pos, std::move(value));
}
void reverse(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return;
int a, b, c;
split(root, l, a, b);
split(b, r - l, b, c);
apply_reverse(b);
root = merge(merge(a, b), c);
}
void reverse() {
apply_reverse(root);
}
void rotate(int l, int m, int r) {
assert(0 <= l && l <= m && m <= r && r <= size());
if (l == m || m == r) return;
int a, b, c, d;
split(root, l, a, b);
split(b, m - l, b, c);
split(c, r - m, c, d);
root = merge(merge(a, c), merge(b, d));
}
T prod(int l, int r) {
assert(0 <= l && l <= r && r <= size());
if (l == r) return Monoid::id();
int a, b, c;
split(root, l, a, b);
split(b, r - l, b, c);
T res = pool[b].prod;
root = merge(merge(a, b), c);
return res;
}
T all_prod() const {
return pool[root].prod;
}
std::vector<T> to_vector() const {
std::vector<T> res;
res.reserve(size());
dump_dfs(root, res);
return res;
}
std::vector<T> to_vector(int l, int r) const {
assert(0 <= l && l <= r && r <= size());
std::vector<T> res;
res.reserve(r - l);
dump_range_dfs(root, l, r, 0, res);
return res;
}
DynamicMonoidArray split_off(int pos) {
assert(0 <= pos && pos <= size());
int l, r;
split(root, pos, l, r);
root = l;
DynamicMonoidArray res;
res.pool.reserve(pool[r].count + 1);
res.root = res.clone_subtree_from(*this, r);
return res;
}
};
} // namespace ds
} // namespace m1une
#line 12 "ds/dynamic_array/rollback_dynamic_monoid_array.hpp"
namespace m1une {
namespace ds {
template <class Monoid>
struct RollbackDynamicMonoidArray {
using T = typename Monoid::value_type;
private:
enum class Kind { insert, erase, set, reverse, rotate, clear };
struct Entry {
Kind kind;
int first;
int second;
int third;
std::optional<T> value;
std::vector<T> values;
};
DynamicMonoidArray<Monoid> _data;
std::vector<Entry> _history;
std::vector<std::size_t> _checkpoints;
void record_insert(int pos, int count) {
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::insert, pos, count, 0, std::nullopt, {}});
}
}
public:
RollbackDynamicMonoidArray() = default;
explicit RollbackDynamicMonoidArray(int n) : _data(n) {}
RollbackDynamicMonoidArray(int n, const T& value) : _data(n, value) {}
explicit RollbackDynamicMonoidArray(const std::vector<T>& values) : _data(values) {}
explicit RollbackDynamicMonoidArray(std::vector<T>&& values) : _data(std::move(values)) {}
template <class U>
requires(!std::same_as<U, T>)
explicit RollbackDynamicMonoidArray(const std::vector<U>& values) : _data(values) {}
RollbackDynamicMonoidArray(std::initializer_list<T> init) : _data(init) {}
int size() const { return _data.size(); }
bool empty() const { return _data.empty(); }
std::size_t node_count() const { return std::size_t(size()); }
void clear() {
Entry entry{Kind::clear, 0, 0, 0, std::nullopt, {}};
if (!_checkpoints.empty()) entry.values = _data.to_vector();
_data.clear();
if (!_checkpoints.empty()) _history.push_back(std::move(entry));
}
void insert(int pos, T value) {
_data.insert(pos, std::move(value));
record_insert(pos, 1);
}
void insert(int pos, const std::vector<T>& values) {
_data.insert(pos, values);
record_insert(pos, int(values.size()));
}
void insert(int pos, std::vector<T>&& values) {
int count = int(values.size());
_data.insert(pos, std::move(values));
record_insert(pos, count);
}
void insert(int pos, std::initializer_list<T> values) {
insert(pos, std::vector<T>(values));
}
void insert(int pos, const RollbackDynamicMonoidArray& other) {
insert(pos, other.to_vector());
}
void insert(int pos, const DynamicMonoidArray<Monoid>& other) {
DynamicMonoidArray<Monoid> copy = other;
insert(pos, copy.to_vector());
}
void push_back(T value) { insert(size(), std::move(value)); }
void push_front(T value) { insert(0, std::move(value)); }
void append(const std::vector<T>& values) { insert(size(), values); }
void append(std::vector<T>&& values) { insert(size(), std::move(values)); }
void append(const RollbackDynamicMonoidArray& other) { insert(size(), other); }
void append(const DynamicMonoidArray<Monoid>& other) { insert(size(), other); }
void erase(int pos) { erase(pos, pos + 1); }
void erase(int left, int right) {
assert(0 <= left && left <= right && right <= size());
Entry entry{Kind::erase, left, 0, 0, std::nullopt, {}};
if (!_checkpoints.empty()) entry.values = _data.to_vector(left, right);
_data.erase(left, right);
if (!_checkpoints.empty()) _history.push_back(std::move(entry));
}
void pop_back() { assert(!empty()); erase(size() - 1); }
void pop_front() { assert(!empty()); erase(0); }
T get(int pos) const { return _data.get(pos); }
T operator[](int pos) const { return get(pos); }
T front() const { assert(!empty()); return get(0); }
T back() const { assert(!empty()); return get(size() - 1); }
void set(int pos, T value) {
Entry entry{Kind::set, pos, 0, 0, std::nullopt, {}};
if (!_checkpoints.empty()) entry.value.emplace(_data.get(pos));
_data.set(pos, std::move(value));
if (!_checkpoints.empty()) _history.push_back(std::move(entry));
}
void set_inplace(int pos, T value) { set(pos, std::move(value)); }
void reverse(int left, int right) {
_data.reverse(left, right);
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::reverse, left, right, 0, std::nullopt, {}});
}
}
void reverse() { reverse(0, size()); }
void rotate(int left, int middle, int right) {
_data.rotate(left, middle, right);
if (!_checkpoints.empty()) {
_history.push_back(Entry{Kind::rotate, left, middle, right, std::nullopt, {}});
}
}
T prod(int left, int right) { return _data.prod(left, right); }
T all_prod() const { return _data.all_prod(); }
std::vector<T> to_vector() { return _data.to_vector(); }
std::vector<T> to_vector() const {
DynamicMonoidArray<Monoid> copy = _data;
return copy.to_vector();
}
std::vector<T> to_vector(int left, int right) { return _data.to_vector(left, right); }
std::vector<T> to_vector(int left, int right) const {
DynamicMonoidArray<Monoid> copy = _data;
return copy.to_vector(left, right);
}
int snapshot() { _checkpoints.push_back(_history.size()); return int(_checkpoints.size()); }
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) { assert(0 <= count); _checkpoints.reserve(count); }
private:
void restore_one() {
Entry entry = std::move(_history.back());
_history.pop_back();
if (entry.kind == Kind::insert) {
_data.erase(entry.first, entry.first + entry.second);
} else if (entry.kind == Kind::erase) {
_data.insert(entry.first, std::move(entry.values));
} else if (entry.kind == Kind::set) {
_data.set(entry.first, std::move(*entry.value));
} else if (entry.kind == Kind::reverse) {
_data.reverse(entry.first, entry.second);
} else if (entry.kind == Kind::rotate) {
_data.rotate(entry.first, entry.first + entry.third - entry.second, entry.third);
} else {
_data.insert(0, std::move(entry.values));
}
}
public:
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() { _history.clear(); _checkpoints.clear(); }
void release() { _data.clear(); _history.clear(); _checkpoints.clear(); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/queue/rollback_queue.hpp"
#line 9 "ds/queue/rollback_queue.hpp"
namespace m1une {
namespace ds {
template <class T>
struct RollbackQueue {
private:
enum class Kind { push, pop, clear };
struct Entry {
Kind kind;
std::optional<T> value;
std::deque<T> values;
};
std::deque<T> _values;
std::vector<Entry> _history;
std::vector<std::size_t> _checkpoints;
std::size_t _stored_values = 0;
public:
RollbackQueue() = default;
int size() const { return int(_values.size()); }
bool empty() const { return _values.empty(); }
std::size_t node_count() const { return _stored_values; }
const T& front() const {
assert(!empty());
return _values.front();
}
const T& back() const {
assert(!empty());
return _values.back();
}
void push(T value) {
if (!_checkpoints.empty()) _history.push_back(Entry{Kind::push, std::nullopt, {}});
_values.push_back(std::move(value));
++_stored_values;
}
void push_back(T value) { push(std::move(value)); }
void pop() {
assert(!empty());
if (_checkpoints.empty()) {
_values.pop_front();
--_stored_values;
} else {
Entry entry{Kind::pop, std::nullopt, {}};
entry.value.emplace(std::move(_values.front()));
_values.pop_front();
_history.push_back(std::move(entry));
}
}
void pop_front() { pop(); }
void clear() {
if (_checkpoints.empty()) {
_stored_values -= _values.size();
_values.clear();
} else {
Entry entry{Kind::clear, std::nullopt, {}};
entry.values = std::move(_values);
_values.clear();
_history.push_back(std::move(entry));
}
}
int snapshot() {
_checkpoints.push_back(_history.size());
return int(_checkpoints.size());
}
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_checkpoints.reserve(count);
}
private:
void restore_one() {
Entry entry = std::move(_history.back());
_history.pop_back();
if (entry.kind == Kind::push) {
_values.pop_back();
--_stored_values;
} else if (entry.kind == Kind::pop) {
_values.push_front(std::move(*entry.value));
} else {
_values = std::move(entry.values);
}
}
public:
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() {
for (const Entry& entry : _history) {
if (entry.value) --_stored_values;
_stored_values -= entry.values.size();
}
_history.clear();
_checkpoints.clear();
}
void release() {
_values.clear();
_history.clear();
_checkpoints.clear();
_stored_values = 0;
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/segtree/rollback_dual_segtree.hpp"
#line 9 "ds/segtree/rollback_dual_segtree.hpp"
#line 12 "ds/segtree/rollback_dual_segtree.hpp"
namespace m1une {
namespace ds {
template <m1une::monoid::IsMonoid Monoid>
struct RollbackDualSegtree {
using T = typename Monoid::value_type;
private:
struct Node {
T value = Monoid::id();
bool has_value = false;
};
int _n = 0;
detail::RollbackJournal<Node> _journal;
template <class U>
static T make_value(const U& value, int index) {
if constexpr (requires(U x) { Monoid::make(x); }) {
return Monoid::make(value);
} else if constexpr (requires(U x, int i) { Monoid::make(x, i); }) {
return Monoid::make(value, index);
} else {
return static_cast<T>(value);
}
}
void initialize(int n) {
assert(0 <= n);
_n = n;
_journal.nodes.assign(std::max(1, 4 * n), Node());
_journal.saved_epoch.assign(_journal.nodes.size(), 0);
}
template <class U>
void build(int node, int left, int right, const std::vector<U>& values) {
if (right - left == 1) {
_journal[node].value = make_value(values[left], left);
_journal[node].has_value = true;
return;
}
int middle = (left + right) >> 1;
build(node << 1, left, middle, values);
build(node << 1 | 1, middle, right, values);
}
void all_apply(int node, const T& value) {
_journal.touch(node);
Node& current = _journal[node];
current.value = current.has_value
? Monoid::op(value, current.value)
: value;
current.has_value = true;
}
void push(int node) {
if (!_journal[node].has_value) return;
T value = _journal[node].value;
all_apply(node << 1, value);
all_apply(node << 1 | 1, value);
_journal.touch(node);
_journal[node].value = Monoid::id();
_journal[node].has_value = false;
}
void set_node(int node, int left, int right, int pos, T value) {
if (right - left == 1) {
_journal.touch(node);
_journal[node].value = std::move(value);
_journal[node].has_value = true;
return;
}
push(node);
int middle = (left + right) >> 1;
if (pos < middle) set_node(node << 1, left, middle, pos, std::move(value));
else set_node(node << 1 | 1, middle, right, pos, std::move(value));
}
void apply_node(int node, int left, int right, int query_left, int query_right, const T& value) {
if (query_right <= left || right <= query_left) return;
if (query_left <= left && right <= query_right) {
all_apply(node, value);
return;
}
push(node);
int middle = (left + right) >> 1;
apply_node(node << 1, left, middle, query_left, query_right, value);
apply_node(node << 1 | 1, middle, right, query_left, query_right, value);
}
T get_node(int node, int left, int right, int pos, T inherited) const {
const Node& current = _journal[node];
if (right - left == 1) {
assert(current.has_value);
return Monoid::op(inherited, current.value);
}
if (current.has_value) inherited = Monoid::op(inherited, current.value);
int middle = (left + right) >> 1;
if (pos < middle) return get_node(node << 1, left, middle, pos, std::move(inherited));
return get_node(node << 1 | 1, middle, right, pos, std::move(inherited));
}
public:
RollbackDualSegtree() { initialize(0); }
explicit RollbackDualSegtree(int n) {
initialize(n);
if (n > 0) {
std::vector<T> values(n, Monoid::id());
build(1, 0, n, values);
}
}
explicit RollbackDualSegtree(const std::vector<T>& values) {
initialize(int(values.size()));
if (_n > 0) build(1, 0, _n, values);
}
template <class U>
requires(!std::same_as<U, T>)
explicit RollbackDualSegtree(const std::vector<U>& values) {
initialize(int(values.size()));
if (_n > 0) build(1, 0, _n, values);
}
int size() const { return _n; }
bool empty() const { return _n == 0; }
std::size_t node_count() const { return _journal.nodes.size(); }
void set(int pos, T value) {
assert(0 <= pos && pos < _n);
set_node(1, 0, _n, pos, std::move(value));
}
void set_inplace(int pos, T value) { set(pos, std::move(value)); }
T get(int pos) const {
assert(0 <= pos && pos < _n);
return get_node(1, 0, _n, pos, Monoid::id());
}
T operator[](int pos) const { return get(pos); }
void apply(int pos, const T& value) { apply(pos, pos + 1, value); }
void apply(int left, int right, const T& value) {
assert(0 <= left && left <= right && right <= _n);
if (left != right) apply_node(1, 0, _n, left, right, value);
}
void apply_inplace(int pos, const T& value) { apply(pos, value); }
void apply_inplace(int left, int right, const T& value) { apply(left, right, value); }
int snapshot() { return _journal.snapshot(); }
int snapshot_count() const { return _journal.snapshot_count(); }
void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
void rollback(int state) { _journal.rollback(state); }
void clear_history() { _journal.clear_history(); }
void release() { _n = 0; _journal.clear(); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/segtree/rollback_dynamic_dual_segtree.hpp"
#line 7 "ds/segtree/rollback_dynamic_dual_segtree.hpp"
#include <numeric>
#line 10 "ds/segtree/rollback_dynamic_dual_segtree.hpp"
#line 1 "ds/segtree/dynamic_segtree_common.hpp"
#line 11 "ds/segtree/dynamic_segtree_common.hpp"
namespace m1une {
namespace ds {
namespace detail {
template <std::integral Index>
using dynamic_size_type = std::make_unsigned_t<Index>;
template <std::integral Index>
constexpr dynamic_size_type<Index> dynamic_distance(Index left, Index right) {
return static_cast<dynamic_size_type<Index>>(right) - static_cast<dynamic_size_type<Index>>(left);
}
template <class Monoid, class Size>
typename Monoid::value_type monoid_repeat(typename Monoid::value_type value, Size count) {
typename Monoid::value_type result = Monoid::id();
while (count != 0) {
if (count & 1) result = Monoid::op(result, value);
count >>= 1;
if (count != 0) value = Monoid::op(value, value);
}
return result;
}
template <class ActedMonoid>
typename ActedMonoid::value_type dynamic_mapping(
const typename ActedMonoid::operator_type& f,
const typename ActedMonoid::value_type& value
) {
using F = typename ActedMonoid::operator_type;
using T = typename ActedMonoid::value_type;
if constexpr (requires(F g, T x, long long ord) { ActedMonoid::mapping(g, x, ord); }) {
return ActedMonoid::mapping(f, value, 0);
} else {
return ActedMonoid::mapping(f, value);
}
}
template <class ActedMonoid, class Size>
typename ActedMonoid::operator_type dynamic_shift(
const typename ActedMonoid::operator_type& f,
Size offset
) {
using F = typename ActedMonoid::operator_type;
if constexpr (requires(F g, long long ord) { ActedMonoid::op_shift(g, ord); }) {
assert(offset <= static_cast<Size>(std::numeric_limits<long long>::max()));
return ActedMonoid::op_shift(f, static_cast<long long>(offset));
} else {
return f;
}
}
template <class Monoid, std::integral Index>
class UniformMonoidDomain {
public:
using T = typename Monoid::value_type;
using size_type = dynamic_size_type<Index>;
private:
struct Level {
size_type small_length;
T small_value;
T large_value;
};
Index _left;
Index _right;
T _initial_value;
std::vector<Level> _levels;
public:
UniformMonoidDomain(Index left, Index right, T initial_value)
: _left(left), _right(right), _initial_value(std::move(initial_value)) {
assert(left <= right);
size_type n = size();
constexpr int digits = std::numeric_limits<size_type>::digits;
_levels.reserve(digits + 1);
for (int depth = 0; depth <= digits; depth++) {
size_type small = depth == digits ? 0 : n >> depth;
size_type large = small;
if (depth != 0) {
bool has_remainder;
if (depth == digits) {
has_remainder = n != 0;
} else {
size_type mask = (size_type(1) << depth) - 1;
has_remainder = (n & mask) != 0;
}
if (has_remainder) large++;
}
_levels.push_back(Level{
small,
monoid_repeat<Monoid>(_initial_value, small),
monoid_repeat<Monoid>(_initial_value, large),
});
}
}
Index left_bound() const {
return _left;
}
Index right_bound() const {
return _right;
}
size_type size() const {
return dynamic_distance(_left, _right);
}
bool empty() const {
return _left == _right;
}
const T& initial_value() const {
return _initial_value;
}
const T& default_product(int depth, Index left, Index right) const {
assert(0 <= depth && depth < int(_levels.size()));
const Level& level = _levels[depth];
size_type length = dynamic_distance(left, right);
if (length == level.small_length) return level.small_value;
assert(length == level.small_length + 1);
return level.large_value;
}
};
} // namespace detail
} // namespace ds
} // namespace m1une
#line 14 "ds/segtree/rollback_dynamic_dual_segtree.hpp"
namespace m1une {
namespace ds {
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct RollbackDynamicDualSegtree {
using T = typename Monoid::value_type;
using index_type = Index;
using size_type = detail::dynamic_size_type<Index>;
private:
struct Node {
T value = Monoid::id();
int left = 0;
int right = 0;
bool has_value = false;
};
Index _left;
Index _right;
T _initial_value;
detail::RollbackJournal<Node> _journal;
int root() const { return _journal[0].left; }
int new_node() { return _journal.emplace(); }
int ensure(int node) { return node ? node : new_node(); }
void all_apply(int node, Index left, Index right, const T& value) {
_journal.touch(node);
Node& current = _journal[node];
if (std::midpoint(left, right) == left) {
T old = current.has_value ? current.value : _initial_value;
current.value = Monoid::op(value, old);
} else {
current.value = current.has_value ? Monoid::op(value, current.value) : value;
}
current.has_value = true;
}
void push(int node, Index left, Index right) {
if (!_journal[node].has_value) return;
Index middle = std::midpoint(left, right);
if (middle == left) return;
T lazy = _journal[node].value;
int left_child = ensure(_journal[node].left);
int right_child = ensure(_journal[node].right);
all_apply(left_child, left, middle, lazy);
all_apply(right_child, middle, right, lazy);
_journal.touch(node);
_journal[node].left = left_child;
_journal[node].right = right_child;
_journal[node].value = Monoid::id();
_journal[node].has_value = false;
}
int set_node(int node, Index left, Index right, Index pos, T value) {
node = ensure(node);
Index middle = std::midpoint(left, right);
if (middle == left) {
_journal.touch(node);
_journal[node].value = std::move(value);
_journal[node].has_value = true;
return node;
}
push(node, left, right);
if (pos < middle) {
int child = set_node(_journal[node].left, left, middle, pos, std::move(value));
_journal.touch(node);
_journal[node].left = child;
} else {
int child = set_node(_journal[node].right, middle, right, pos, std::move(value));
_journal.touch(node);
_journal[node].right = child;
}
return node;
}
int apply_node(int node, Index left, Index right, Index query_left, Index query_right, const T& value) {
if (query_right <= left || right <= query_left) return node;
node = ensure(node);
if (query_left <= left && right <= query_right) {
all_apply(node, left, right, value);
return node;
}
push(node, left, right);
Index middle = std::midpoint(left, right);
int left_child = apply_node(_journal[node].left, left, middle, query_left, query_right, value);
int right_child = apply_node(_journal[node].right, middle, right, query_left, query_right, value);
_journal.touch(node);
_journal[node].left = left_child;
_journal[node].right = right_child;
return node;
}
public:
RollbackDynamicDualSegtree()
: RollbackDynamicDualSegtree(Index(0), Index(0), Monoid::id()) {}
explicit RollbackDynamicDualSegtree(Index n)
: RollbackDynamicDualSegtree(Index(0), n, Monoid::id()) {
if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
}
RollbackDynamicDualSegtree(Index left, Index right)
: RollbackDynamicDualSegtree(left, right, Monoid::id()) {}
RollbackDynamicDualSegtree(Index left, Index right, T initial_value)
: _left(left), _right(right), _initial_value(std::move(initial_value)) {
assert(left <= right);
_journal.emplace();
}
size_type size() const { return detail::dynamic_distance(_left, _right); }
bool empty() const { return _left == _right; }
Index left_bound() const { return _left; }
Index right_bound() const { return _right; }
const T& initial_value() const { return _initial_value; }
std::size_t node_count() const { return _journal.nodes.size() - 1; }
void reserve(std::size_t node_capacity) {
_journal.nodes.reserve(node_capacity + 1);
_journal.saved_epoch.reserve(node_capacity + 1);
}
void set(Index pos, T value) {
assert(_left <= pos && pos < _right);
int next_root = set_node(root(), _left, _right, pos, std::move(value));
if (next_root != root()) {
_journal.touch(0);
_journal[0].left = next_root;
}
}
void set_inplace(Index pos, T value) { set(pos, std::move(value)); }
T get(Index pos) const {
assert(_left <= pos && pos < _right);
int node = root();
Index left = _left;
Index right = _right;
T inherited = Monoid::id();
while (node) {
Index middle = std::midpoint(left, right);
if (middle == left) {
T value = _journal[node].has_value ? _journal[node].value : _initial_value;
return Monoid::op(inherited, value);
}
if (_journal[node].has_value) inherited = Monoid::op(inherited, _journal[node].value);
if (pos < middle) {
node = _journal[node].left;
right = middle;
} else {
node = _journal[node].right;
left = middle;
}
}
return Monoid::op(inherited, _initial_value);
}
T operator[](Index pos) const { return get(pos); }
void apply(Index pos, const T& value) { apply(pos, pos + 1, value); }
void apply(Index left, Index right, const T& value) {
assert(_left <= left && left <= right && right <= _right);
if (left == right) return;
int next_root = apply_node(root(), _left, _right, left, right, value);
if (next_root != root()) {
_journal.touch(0);
_journal[0].left = next_root;
}
}
void apply_inplace(Index pos, const T& value) { apply(pos, value); }
void apply_inplace(Index left, Index right, const T& value) { apply(left, right, value); }
int snapshot() { return _journal.snapshot(); }
int snapshot_count() const { return _journal.snapshot_count(); }
void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
void rollback(int state) { _journal.rollback(state); }
void clear_history() { _journal.clear_history(); }
void release() { _journal.clear(); _journal.emplace(); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/segtree/rollback_dynamic_lazy_segtree.hpp"
#line 12 "ds/segtree/rollback_dynamic_lazy_segtree.hpp"
#line 16 "ds/segtree/rollback_dynamic_lazy_segtree.hpp"
namespace m1une {
namespace ds {
// A sparse lazy segment tree over an integral half-open interval.
template <m1une::acted_monoid::IsActedMonoid ActedMonoid, std::integral Index = long long>
requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct RollbackDynamicLazySegtree {
using T = typename ActedMonoid::value_type;
using F = typename ActedMonoid::operator_type;
using index_type = Index;
using size_type = detail::dynamic_size_type<Index>;
private:
struct Node {
T val;
F lazy;
int left;
int right;
bool has_lazy;
explicit Node(T value)
: val(std::move(value)),
lazy(ActedMonoid::op_id()),
left(0),
right(0),
has_lazy(false) {}
};
detail::UniformMonoidDomain<ActedMonoid, Index> _domain;
detail::RollbackJournal<Node> _journal;
int root() const { return _journal[0].left; }
int new_node(Index left, Index right, int depth) {
assert(_journal.nodes.size() < std::size_t(std::numeric_limits<int>::max()));
return _journal.emplace(_domain.default_product(depth, left, right));
}
const T& value(int t, Index left, Index right, int depth) const {
if (t) return _journal[t].val;
return _domain.default_product(depth, left, right);
}
void all_apply(int& t, Index left, Index right, int depth, const F& f) {
if (!t) t = new_node(left, right, depth);
_journal.touch(t);
Node& node = _journal[t];
node.val = detail::dynamic_mapping<ActedMonoid>(f, node.val);
if (std::midpoint(left, right) != left) {
node.lazy = ActedMonoid::op_comp(f, node.lazy);
node.has_lazy = true;
}
}
void push(int t, Index left, Index right, int depth) {
if (!_journal[t].has_lazy) return;
Index middle = std::midpoint(left, right);
if (middle == left) return;
F lazy = _journal[t].lazy;
int left_child = _journal[t].left;
int right_child = _journal[t].right;
all_apply(left_child, left, middle, depth + 1, lazy);
all_apply(
right_child,
middle,
right,
depth + 1,
detail::dynamic_shift<ActedMonoid>(lazy, detail::dynamic_distance(left, middle))
);
_journal.touch(t);
Node& node = _journal[t];
node.left = left_child;
node.right = right_child;
node.lazy = ActedMonoid::op_id();
node.has_lazy = false;
}
void update(int t, Index left, Index right, int depth) {
_journal.touch(t);
Index middle = std::midpoint(left, right);
_journal[t].val = ActedMonoid::op(
value(_journal[t].left, left, middle, depth + 1),
value(_journal[t].right, middle, right, depth + 1)
);
}
int set_node(int t, Index left, Index right, int depth, Index p, T x) {
if (!t) t = new_node(left, right, depth);
Index middle = std::midpoint(left, right);
if (middle == left) {
_journal.touch(t);
Node& node = _journal[t];
node.val = std::move(x);
node.lazy = ActedMonoid::op_id();
node.has_lazy = false;
return t;
}
push(t, left, right, depth);
if (p < middle) {
int child = set_node(_journal[t].left, left, middle, depth + 1, p, std::move(x));
_journal.touch(t);
_journal[t].left = child;
} else {
int child = set_node(_journal[t].right, middle, right, depth + 1, p, std::move(x));
_journal.touch(t);
_journal[t].right = child;
}
update(t, left, right, depth);
return t;
}
int apply_node(
int t,
Index left,
Index right,
int depth,
Index query_left,
Index query_right,
const F& f
) {
if (query_right <= left || right <= query_left) return t;
if (query_left <= left && right <= query_right) {
all_apply(
t,
left,
right,
depth,
detail::dynamic_shift<ActedMonoid>(f, detail::dynamic_distance(query_left, left))
);
return t;
}
if (!t) t = new_node(left, right, depth);
push(t, left, right, depth);
Index middle = std::midpoint(left, right);
int left_child = apply_node(_journal[t].left, left, middle, depth + 1, query_left, query_right, f);
int right_child = apply_node(_journal[t].right, middle, right, depth + 1, query_left, query_right, f);
_journal.touch(t);
_journal[t].left = left_child;
_journal[t].right = right_child;
update(t, left, right, depth);
return t;
}
F compose_for_child(const F& inherited, int t, size_type offset) const {
F shifted = detail::dynamic_shift<ActedMonoid>(inherited, offset);
if (!t || !_journal[t].has_lazy) return shifted;
return ActedMonoid::op_comp(
shifted,
detail::dynamic_shift<ActedMonoid>(_journal[t].lazy, offset)
);
}
T prod_node(
int t,
Index left,
Index right,
int depth,
Index query_left,
Index query_right,
const F& inherited
) const {
if (query_right <= left || right <= query_left) return ActedMonoid::id();
if (query_left <= left && right <= query_right) {
return detail::dynamic_mapping<ActedMonoid>(
inherited,
value(t, left, right, depth)
);
}
Index middle = std::midpoint(left, right);
return ActedMonoid::op(
prod_node(
t ? _journal[t].left : 0,
left,
middle,
depth + 1,
query_left,
query_right,
compose_for_child(inherited, t, 0)
),
prod_node(
t ? _journal[t].right : 0,
middle,
right,
depth + 1,
query_left,
query_right,
compose_for_child(inherited, t, detail::dynamic_distance(left, middle))
)
);
}
template <class G>
Index max_right_node(
int t,
Index left,
Index right,
int depth,
Index query_left,
T& product,
const F& inherited,
G& predicate
) const {
if (right <= query_left) return right;
if (query_left <= left) {
T next = ActedMonoid::op(
product,
detail::dynamic_mapping<ActedMonoid>(
inherited,
value(t, left, right, depth)
)
);
if (predicate(next)) {
product = std::move(next);
return right;
}
Index middle = std::midpoint(left, right);
if (middle == left) return left;
}
Index middle = std::midpoint(left, right);
Index result = max_right_node(
t ? _journal[t].left : 0,
left,
middle,
depth + 1,
query_left,
product,
compose_for_child(inherited, t, 0),
predicate
);
if (result < middle) return result;
return max_right_node(
t ? _journal[t].right : 0,
middle,
right,
depth + 1,
query_left,
product,
compose_for_child(inherited, t, detail::dynamic_distance(left, middle)),
predicate
);
}
template <class G>
Index min_left_node(
int t,
Index left,
Index right,
int depth,
Index query_right,
T& product,
const F& inherited,
G& predicate
) const {
if (query_right <= left) return left;
if (right <= query_right) {
T next = ActedMonoid::op(
detail::dynamic_mapping<ActedMonoid>(
inherited,
value(t, left, right, depth)
),
product
);
if (predicate(next)) {
product = std::move(next);
return left;
}
Index middle = std::midpoint(left, right);
if (middle == left) return right;
}
Index middle = std::midpoint(left, right);
Index result = min_left_node(
t ? _journal[t].right : 0,
middle,
right,
depth + 1,
query_right,
product,
compose_for_child(inherited, t, detail::dynamic_distance(left, middle)),
predicate
);
if (middle < result) return result;
return min_left_node(
t ? _journal[t].left : 0,
left,
middle,
depth + 1,
query_right,
product,
compose_for_child(inherited, t, 0),
predicate
);
}
public:
RollbackDynamicLazySegtree()
: RollbackDynamicLazySegtree(Index(0), Index(0), ActedMonoid::id()) {}
explicit RollbackDynamicLazySegtree(Index n)
: RollbackDynamicLazySegtree(Index(0), n, ActedMonoid::id()) {
if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
}
RollbackDynamicLazySegtree(Index left, Index right)
: RollbackDynamicLazySegtree(left, right, ActedMonoid::id()) {}
RollbackDynamicLazySegtree(Index left, Index right, T initial_value)
: _domain(left, right, std::move(initial_value)) {
_journal.emplace(ActedMonoid::id());
}
size_type size() const {
return _domain.size();
}
bool empty() const {
return _domain.empty();
}
Index left_bound() const {
return _domain.left_bound();
}
Index right_bound() const {
return _domain.right_bound();
}
const T& initial_value() const {
return _domain.initial_value();
}
void reserve(std::size_t node_capacity) {
assert(node_capacity < std::numeric_limits<std::size_t>::max());
_journal.nodes.reserve(node_capacity + 1);
_journal.saved_epoch.reserve(node_capacity + 1);
}
std::size_t node_count() const {
return _journal.nodes.size() - 1;
}
void clear() {
if (_journal.snapshot_count() == 0) {
_journal.clear();
_journal.emplace(ActedMonoid::id());
return;
}
_journal.touch(0);
_journal[0].left = 0;
}
void set(Index p, T x) {
assert(left_bound() <= p && p < right_bound());
int next_root = set_node(root(), left_bound(), right_bound(), 0, p, std::move(x));
if (next_root != root()) {
_journal.touch(0);
_journal[0].left = next_root;
}
}
T get(Index p) const {
assert(left_bound() <= p && p < right_bound());
return prod(p, p + 1);
}
T operator[](Index p) const {
return get(p);
}
T prod(Index left, Index right) const {
assert(left_bound() <= left && left <= right && right <= right_bound());
if (left == right) return ActedMonoid::id();
return prod_node(
root(),
left_bound(),
right_bound(),
0,
left,
right,
ActedMonoid::op_id()
);
}
T all_prod() const {
return value(root(), left_bound(), right_bound(), 0);
}
void apply(Index p, const F& f) {
assert(left_bound() <= p && p < right_bound());
apply(p, p + 1, f);
}
void apply(Index left, Index right, const F& f) {
assert(left_bound() <= left && left <= right && right <= right_bound());
if (left == right) return;
int next_root = apply_node(
root(), left_bound(), right_bound(), 0, left, right, f
);
if (next_root != root()) {
_journal.touch(0);
_journal[0].left = next_root;
}
}
template <class G>
Index max_right(Index left, G predicate) const {
assert(left_bound() <= left && left <= right_bound());
assert(predicate(ActedMonoid::id()));
if (left == right_bound()) return right_bound();
T product = ActedMonoid::id();
return max_right_node(
root(),
left_bound(),
right_bound(),
0,
left,
product,
ActedMonoid::op_id(),
predicate
);
}
template <class G>
Index min_left(Index right, G predicate) const {
assert(left_bound() <= right && right <= right_bound());
assert(predicate(ActedMonoid::id()));
if (right == left_bound()) return left_bound();
T product = ActedMonoid::id();
return min_left_node(
root(),
left_bound(),
right_bound(),
0,
right,
product,
ActedMonoid::op_id(),
predicate
);
}
void set_inplace(Index p, T x) { set(p, std::move(x)); }
void apply_inplace(Index p, const F& f) { apply(p, f); }
void apply_inplace(Index left, Index right, const F& f) { apply(left, right, f); }
int snapshot() { return _journal.snapshot(); }
int snapshot_count() const { return _journal.snapshot_count(); }
void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
void rollback(int state) { _journal.rollback(state); }
void clear_history() { _journal.clear_history(); }
void release() { _journal.clear(); _journal.emplace(ActedMonoid::id()); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/segtree/rollback_dynamic_segtree.hpp"
#include <array>
#line 11 "ds/segtree/rollback_dynamic_segtree.hpp"
#line 15 "ds/segtree/rollback_dynamic_segtree.hpp"
namespace m1une {
namespace ds {
template <m1une::monoid::IsMonoid Monoid, std::integral Index = long long>
requires(!std::same_as<std::remove_cv_t<Index>, bool>)
struct RollbackDynamicSegtree {
using T = typename Monoid::value_type;
using index_type = Index;
using size_type = detail::dynamic_size_type<Index>;
private:
struct Node {
T value = Monoid::id();
int left = 0;
int right = 0;
};
static constexpr int path_capacity = std::numeric_limits<size_type>::digits + 1;
detail::UniformMonoidDomain<Monoid, Index> _domain;
detail::RollbackJournal<Node> _journal;
int root() const { return _journal[0].left; }
int new_node() { return _journal.emplace(); }
const T& value(int node, Index left, Index right, int depth) const {
if (node) return _journal[node].value;
return _domain.default_product(depth, left, right);
}
void update(int node, Index left, Index right, int depth) {
Index middle = std::midpoint(left, right);
_journal.touch(node);
_journal[node].value = Monoid::op(
value(_journal[node].left, left, middle, depth + 1),
value(_journal[node].right, middle, right, depth + 1)
);
}
T prod_node(int node, Index left, Index right, int depth, Index query_left, Index query_right) const {
if (query_right <= left || right <= query_left) return Monoid::id();
if (query_left <= left && right <= query_right) return value(node, left, right, depth);
Index middle = std::midpoint(left, right);
return Monoid::op(
prod_node(node ? _journal[node].left : 0, left, middle, depth + 1, query_left, query_right),
prod_node(node ? _journal[node].right : 0, middle, right, depth + 1, query_left, query_right)
);
}
template <class Predicate>
Index max_right_node(int node, Index left, Index right, int depth, Index query_left, T& product,
Predicate& predicate) const {
if (right <= query_left) return right;
if (query_left <= left) {
T next = Monoid::op(product, value(node, left, right, depth));
if (predicate(next)) {
product = std::move(next);
return right;
}
Index middle = std::midpoint(left, right);
if (middle == left) return left;
}
Index middle = std::midpoint(left, right);
Index result = max_right_node(node ? _journal[node].left : 0, left, middle, depth + 1,
query_left, product, predicate);
if (result < middle) return result;
return max_right_node(node ? _journal[node].right : 0, middle, right, depth + 1,
query_left, product, predicate);
}
template <class Predicate>
Index min_left_node(int node, Index left, Index right, int depth, Index query_right, T& product,
Predicate& predicate) const {
if (query_right <= left) return left;
if (right <= query_right) {
T next = Monoid::op(value(node, left, right, depth), product);
if (predicate(next)) {
product = std::move(next);
return left;
}
Index middle = std::midpoint(left, right);
if (middle == left) return right;
}
Index middle = std::midpoint(left, right);
Index result = min_left_node(node ? _journal[node].right : 0, middle, right, depth + 1,
query_right, product, predicate);
if (middle < result) return result;
return min_left_node(node ? _journal[node].left : 0, left, middle, depth + 1,
query_right, product, predicate);
}
public:
RollbackDynamicSegtree() : RollbackDynamicSegtree(Index(0), Index(0)) {}
explicit RollbackDynamicSegtree(Index n) : RollbackDynamicSegtree(Index(0), n) {
if constexpr (std::signed_integral<Index>) assert(Index(0) <= n);
}
RollbackDynamicSegtree(Index left, Index right)
: RollbackDynamicSegtree(left, right, Monoid::id()) {}
RollbackDynamicSegtree(Index left, Index right, T initial_value)
: _domain(left, right, std::move(initial_value)) {
_journal.emplace();
}
size_type size() const { return _domain.size(); }
bool empty() const { return _domain.empty(); }
Index left_bound() const { return _domain.left_bound(); }
Index right_bound() const { return _domain.right_bound(); }
const T& initial_value() const { return _domain.initial_value(); }
void reserve(std::size_t node_capacity) {
_journal.nodes.reserve(node_capacity + 1);
_journal.saved_epoch.reserve(node_capacity + 1);
}
std::size_t node_count() const { return _journal.nodes.size() - 1; }
void set(Index pos, T x) {
assert(left_bound() <= pos && pos < right_bound());
if (!root()) {
int node = new_node();
_journal.touch(0);
_journal[0].left = node;
}
std::array<int, path_capacity> path;
std::array<Index, path_capacity> path_left;
std::array<Index, path_capacity> path_right;
int depth = 0;
int node = root();
Index left = left_bound();
Index right = right_bound();
while (true) {
path[depth] = node;
path_left[depth] = left;
path_right[depth] = right;
++depth;
Index middle = std::midpoint(left, right);
if (middle == left) break;
if (pos < middle) {
if (!_journal[node].left) {
int child = new_node();
_journal.touch(node);
_journal[node].left = child;
}
node = _journal[node].left;
right = middle;
} else {
if (!_journal[node].right) {
int child = new_node();
_journal.touch(node);
_journal[node].right = child;
}
node = _journal[node].right;
left = middle;
}
}
_journal.touch(node);
_journal[node].value = std::move(x);
for (int index = depth - 2; index >= 0; --index) {
update(path[index], path_left[index], path_right[index], index);
}
}
void set_inplace(Index pos, T x) { set(pos, std::move(x)); }
T get(Index pos) const {
assert(left_bound() <= pos && pos < right_bound());
int node = root();
Index left = left_bound();
Index right = right_bound();
int depth = 0;
while (node) {
Index middle = std::midpoint(left, right);
if (middle == left) return value(node, left, right, depth);
if (pos < middle) {
node = _journal[node].left;
right = middle;
} else {
node = _journal[node].right;
left = middle;
}
++depth;
}
return initial_value();
}
T operator[](Index pos) const { return get(pos); }
T prod(Index left, Index right) const {
assert(left_bound() <= left && left <= right && right <= right_bound());
if (left == right) return Monoid::id();
return prod_node(root(), left_bound(), right_bound(), 0, left, right);
}
T all_prod() const { return value(root(), left_bound(), right_bound(), 0); }
template <class Predicate>
Index max_right(Index left, Predicate predicate) const {
assert(left_bound() <= left && left <= right_bound());
assert(predicate(Monoid::id()));
if (left == right_bound()) return right_bound();
T product = Monoid::id();
return max_right_node(root(), left_bound(), right_bound(), 0, left, product, predicate);
}
template <class Predicate>
Index min_left(Index right, Predicate predicate) const {
assert(left_bound() <= right && right <= right_bound());
assert(predicate(Monoid::id()));
if (right == left_bound()) return left_bound();
T product = Monoid::id();
return min_left_node(root(), left_bound(), right_bound(), 0, right, product, predicate);
}
int snapshot() { return _journal.snapshot(); }
int snapshot_count() const { return _journal.snapshot_count(); }
void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
void rollback(int state) { _journal.rollback(state); }
void clear_history() { _journal.clear_history(); }
void release() { _journal.clear(); _journal.emplace(); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/segtree/rollback_lazy_segtree.hpp"
#include <bit>
#line 9 "ds/segtree/rollback_lazy_segtree.hpp"
#line 1 "math/bit_ceil.hpp"
namespace m1une {
namespace math {
template <typename T>
constexpr T bit_ceil(T n) {
if (n <= 1) return 1;
T x = 1;
while (x < n) x <<= 1;
return x;
}
} // namespace math
} // namespace m1une
#line 13 "ds/segtree/rollback_lazy_segtree.hpp"
namespace m1une {
namespace ds {
template <m1une::acted_monoid::IsActedMonoid ActedMonoid>
struct RollbackLazySegtree {
using T = typename ActedMonoid::value_type;
using F = typename ActedMonoid::operator_type;
private:
struct Node {
T value = ActedMonoid::id();
F lazy = ActedMonoid::op_id();
bool has_lazy = false;
};
int _n = 0;
int _size = 1;
int _log = 0;
detail::RollbackJournal<Node> _journal;
static T mapping_at(const F& f, const T& value, long long ordinal) {
if constexpr (requires(F g, T x, long long i) { ActedMonoid::mapping(g, x, i); }) {
return ActedMonoid::mapping(f, value, ordinal);
} else {
return ActedMonoid::mapping(f, value);
}
}
static F shift_operator(const F& f, long long ordinal) {
if constexpr (requires(F g, long long i) { ActedMonoid::op_shift(g, i); }) {
return ActedMonoid::op_shift(f, ordinal);
} else {
return f;
}
}
template <class U>
static T make_value(const U& value, int index) {
if constexpr (requires(U x) { ActedMonoid::make(x); }) {
return ActedMonoid::make(value);
} else if constexpr (requires(U x, int i) { ActedMonoid::make(x, i); }) {
return ActedMonoid::make(value, index);
} else {
return static_cast<T>(value);
}
}
int node_length(int node) const {
int level = std::bit_width(static_cast<unsigned int>(node)) - 1;
return _size >> level;
}
int node_left(int node) const {
int level = std::bit_width(static_cast<unsigned int>(node)) - 1;
int length = _size >> level;
return (node - (1 << level)) * length;
}
void update(int node) {
_journal.touch(node);
_journal[node].value = ActedMonoid::op(
_journal[node << 1].value,
_journal[node << 1 | 1].value
);
}
void all_apply(int node, const F& f) {
_journal.touch(node);
_journal[node].value = mapping_at(f, _journal[node].value, 0);
if (node < _size) {
_journal[node].lazy = ActedMonoid::op_comp(f, _journal[node].lazy);
_journal[node].has_lazy = true;
}
}
void push(int node) {
if (!_journal[node].has_lazy) return;
F lazy = _journal[node].lazy;
all_apply(node << 1, lazy);
all_apply(node << 1 | 1, shift_operator(lazy, node_length(node) / 2));
_journal.touch(node);
_journal[node].lazy = ActedMonoid::op_id();
_journal[node].has_lazy = false;
}
template <class U>
void build(const std::vector<U>& values) {
_n = int(values.size());
_size = int(m1une::math::bit_ceil(static_cast<unsigned int>(_n)));
_log = 0;
while ((1U << _log) < static_cast<unsigned int>(_size)) ++_log;
_journal.nodes.assign(2 * _size, Node());
_journal.saved_epoch.assign(_journal.nodes.size(), 0);
for (int index = 0; index < _n; ++index) {
_journal[_size + index].value = make_value(values[index], index);
}
for (int node = _size - 1; node > 0; --node) {
_journal[node].value = ActedMonoid::op(
_journal[node << 1].value,
_journal[node << 1 | 1].value
);
}
}
public:
RollbackLazySegtree() { build(std::vector<T>()); }
explicit RollbackLazySegtree(int n) {
assert(0 <= n);
build(std::vector<T>(n, ActedMonoid::id()));
}
explicit RollbackLazySegtree(const std::vector<T>& values) { build(values); }
explicit RollbackLazySegtree(std::vector<T>&& values) { build(values); }
template <class U>
requires(!std::same_as<U, T>)
explicit RollbackLazySegtree(const std::vector<U>& values) { build(values); }
int size() const { return _n; }
bool empty() const { return _n == 0; }
std::size_t node_count() const { return _journal.nodes.size(); }
void set(int pos, T value) {
assert(0 <= pos && pos < _n);
int node = pos + _size;
for (int level = _log; level >= 1; --level) push(node >> level);
_journal.touch(node);
_journal[node].value = std::move(value);
for (int level = 1; level <= _log; ++level) update(node >> level);
}
void set_inplace(int pos, T value) { set(pos, std::move(value)); }
T get(int pos) {
assert(0 <= pos && pos < _n);
int node = pos + _size;
for (int level = _log; level >= 1; --level) push(node >> level);
return _journal[node].value;
}
T operator[](int pos) { return get(pos); }
T prod(int left, int right) {
assert(0 <= left && left <= right && right <= _n);
if (left == right) return ActedMonoid::id();
left += _size;
right += _size;
for (int level = _log; level >= 1; --level) {
if (((left >> level) << level) != left) push(left >> level);
if (((right >> level) << level) != right) push((right - 1) >> level);
}
T left_product = ActedMonoid::id();
T right_product = ActedMonoid::id();
while (left < right) {
if (left & 1) left_product = ActedMonoid::op(left_product, _journal[left++].value);
if (right & 1) right_product = ActedMonoid::op(_journal[--right].value, right_product);
left >>= 1;
right >>= 1;
}
return ActedMonoid::op(left_product, right_product);
}
T all_prod() const { return _journal[1].value; }
std::vector<T> to_vector() {
for (int node = 1; node < _size; ++node) push(node);
std::vector<T> result;
result.reserve(_n);
for (int index = 0; index < _n; ++index) result.push_back(_journal[_size + index].value);
return result;
}
std::vector<T> to_vector(int left, int right) {
assert(0 <= left && left <= right && right <= _n);
std::vector<T> result;
result.reserve(right - left);
for (int index = left; index < right; ++index) result.push_back(get(index));
return result;
}
void apply(int pos, const F& f) {
assert(0 <= pos && pos < _n);
int node = pos + _size;
for (int level = _log; level >= 1; --level) push(node >> level);
_journal.touch(node);
_journal[node].value = mapping_at(f, _journal[node].value, 0);
for (int level = 1; level <= _log; ++level) update(node >> level);
}
void apply(int left, int right, const F& f) {
assert(0 <= left && left <= right && right <= _n);
if (left == right) return;
int base_left = left;
left += _size;
right += _size;
for (int level = _log; level >= 1; --level) {
if (((left >> level) << level) != left) push(left >> level);
if (((right >> level) << level) != right) push((right - 1) >> level);
}
int saved_left = left;
int saved_right = right;
while (left < right) {
if (left & 1) {
all_apply(left, shift_operator(f, node_left(left) - base_left));
++left;
}
if (right & 1) {
--right;
all_apply(right, shift_operator(f, node_left(right) - base_left));
}
left >>= 1;
right >>= 1;
}
left = saved_left;
right = saved_right;
for (int level = 1; level <= _log; ++level) {
if (((left >> level) << level) != left) update(left >> level);
if (((right >> level) << level) != right) update((right - 1) >> level);
}
}
void apply_inplace(int pos, const F& f) { apply(pos, f); }
void apply_inplace(int left, int right, const F& f) { apply(left, right, f); }
template <class Predicate>
int max_right(int left, Predicate predicate) {
assert(0 <= left && left <= _n);
assert(predicate(ActedMonoid::id()));
if (left == _n) return _n;
int node = left + _size;
for (int level = _log; level >= 1; --level) push(node >> level);
T product = ActedMonoid::id();
do {
while ((node & 1) == 0) node >>= 1;
T next = ActedMonoid::op(product, _journal[node].value);
if (!predicate(next)) {
while (node < _size) {
push(node);
node <<= 1;
next = ActedMonoid::op(product, _journal[node].value);
if (predicate(next)) {
product = std::move(next);
++node;
}
}
return node - _size;
}
product = std::move(next);
++node;
} while ((node & -node) != node);
return _n;
}
template <class Predicate>
int min_left(int right, Predicate predicate) {
assert(0 <= right && right <= _n);
assert(predicate(ActedMonoid::id()));
if (right == 0) return 0;
int node = right + _size;
for (int level = _log; level >= 1; --level) push((node - 1) >> level);
T product = ActedMonoid::id();
do {
--node;
while (node > 1 && (node & 1)) node >>= 1;
T next = ActedMonoid::op(_journal[node].value, product);
if (!predicate(next)) {
while (node < _size) {
push(node);
node = node << 1 | 1;
next = ActedMonoid::op(_journal[node].value, product);
if (predicate(next)) {
product = std::move(next);
--node;
}
}
return node + 1 - _size;
}
product = std::move(next);
} while ((node & -node) != node);
return 0;
}
int snapshot() { return _journal.snapshot(); }
int snapshot_count() const { return _journal.snapshot_count(); }
void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
void rollback(int state) { _journal.rollback(state); }
void clear_history() { _journal.clear_history(); }
void release() { _n = 0; _size = 1; _log = 0; _journal.clear(); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/segtree/rollback_segtree.hpp"
#line 10 "ds/segtree/rollback_segtree.hpp"
#line 12 "ds/segtree/rollback_segtree.hpp"
namespace m1une {
namespace ds {
template <m1une::monoid::IsMonoid Monoid>
struct RollbackSegtree {
using T = typename Monoid::value_type;
private:
struct Entry {
int pos;
T value;
};
struct Checkpoint {
std::size_t change_size;
std::uint64_t epoch;
};
int _n = 0;
int _size = 1;
std::vector<T> _data = std::vector<T>(2, Monoid::id());
std::vector<Entry> _history;
std::vector<Checkpoint> _checkpoints;
std::vector<std::uint64_t> _saved_epoch;
std::uint64_t _next_epoch = 1;
std::uint64_t new_epoch() {
if (_next_epoch == 0) {
std::fill(_saved_epoch.begin(), _saved_epoch.end(), 0);
_next_epoch = 1;
}
return _next_epoch++;
}
template <class U>
static T make_value(const U& value, int index) {
if constexpr (requires(U x) { Monoid::make(x); }) {
return Monoid::make(value);
} else if constexpr (requires(U x, int i) { Monoid::make(x, i); }) {
return Monoid::make(value, index);
} else {
return static_cast<T>(value);
}
}
void assign(int pos, T value) {
int node = pos + _size;
_data[node] = std::move(value);
while (node >>= 1) {
_data[node] = Monoid::op(_data[node << 1], _data[node << 1 | 1]);
}
}
template <class U>
void build(const std::vector<U>& values) {
_n = int(values.size());
_size = 1;
while (_size < _n) _size <<= 1;
_data.assign(2 * _size, Monoid::id());
_saved_epoch.assign(_n, 0);
for (int index = 0; index < _n; ++index) {
_data[_size + index] = make_value(values[index], index);
}
for (int node = _size - 1; node > 0; --node) {
_data[node] = Monoid::op(_data[node << 1], _data[node << 1 | 1]);
}
}
public:
RollbackSegtree() = default;
explicit RollbackSegtree(int n) { assert(0 <= n); build(std::vector<T>(n, Monoid::id())); }
explicit RollbackSegtree(const std::vector<T>& values) { build(values); }
explicit RollbackSegtree(std::vector<T>&& values) { build(values); }
template <class U>
requires(!std::same_as<U, T>)
explicit RollbackSegtree(const std::vector<U>& values) { build(values); }
int size() const { return _n; }
bool empty() const { return _n == 0; }
std::size_t node_count() const { return _data.size(); }
void set(int pos, T value) {
assert(0 <= pos && pos < _n);
if (!_checkpoints.empty() && _saved_epoch[pos] != _checkpoints.back().epoch) {
_saved_epoch[pos] = _checkpoints.back().epoch;
_history.push_back(Entry{pos, get(pos)});
}
assign(pos, std::move(value));
}
void set_inplace(int pos, T value) { set(pos, std::move(value)); }
T get(int pos) const {
assert(0 <= pos && pos < _n);
return _data[_size + pos];
}
T operator[](int pos) const { return get(pos); }
T prod(int left, int right) const {
assert(0 <= left && left <= right && right <= _n);
T left_product = Monoid::id();
T right_product = Monoid::id();
for (left += _size, right += _size; left < right; left >>= 1, right >>= 1) {
if (left & 1) left_product = Monoid::op(left_product, _data[left++]);
if (right & 1) right_product = Monoid::op(_data[--right], right_product);
}
return Monoid::op(left_product, right_product);
}
T all_prod() const { return _data[1]; }
std::vector<T> to_vector() const { return to_vector(0, _n); }
std::vector<T> to_vector(int left, int right) const {
assert(0 <= left && left <= right && right <= _n);
return std::vector<T>(_data.begin() + _size + left, _data.begin() + _size + right);
}
template <class Predicate>
int max_right(int left, Predicate predicate) const {
assert(0 <= left && left <= _n);
assert(predicate(Monoid::id()));
if (left == _n) return _n;
int node = left + _size;
T product = Monoid::id();
do {
while ((node & 1) == 0) node >>= 1;
T next = Monoid::op(product, _data[node]);
if (!predicate(next)) {
while (node < _size) {
node <<= 1;
next = Monoid::op(product, _data[node]);
if (predicate(next)) {
product = std::move(next);
++node;
}
}
return std::min(_n, node - _size);
}
product = std::move(next);
++node;
} while ((node & -node) != node);
return _n;
}
template <class Predicate>
int min_left(int right, Predicate predicate) const {
assert(0 <= right && right <= _n);
assert(predicate(Monoid::id()));
if (right == 0) return 0;
int node = right + _size;
T product = Monoid::id();
do {
--node;
while (node > 1 && (node & 1)) node >>= 1;
T next = Monoid::op(_data[node], product);
if (!predicate(next)) {
while (node < _size) {
node = node << 1 | 1;
next = Monoid::op(_data[node], product);
if (predicate(next)) {
product = std::move(next);
--node;
}
}
return std::max(0, node + 1 - _size);
}
product = std::move(next);
} while ((node & -node) != node);
return 0;
}
int snapshot() {
_checkpoints.push_back(Checkpoint{_history.size(), new_epoch()});
return int(_checkpoints.size());
}
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) { assert(0 <= count); _checkpoints.reserve(count); }
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1].change_size) {
Entry entry = std::move(_history.back());
_history.pop_back();
assign(entry.pos, std::move(entry.value));
}
_checkpoints.resize(state);
_checkpoints.back().epoch = new_epoch();
}
void clear_history() {
_history.clear();
_checkpoints.clear();
std::fill(_saved_epoch.begin(), _saved_epoch.end(), 0);
}
void release() {
_n = 0;
_size = 1;
_data.assign(2, Monoid::id());
_history.clear();
_checkpoints.clear();
_saved_epoch.clear();
_next_epoch = 1;
}
};
} // namespace ds
} // namespace m1une
#line 1 "ds/segtree/rollback_segtree_beats.hpp"
#line 8 "ds/segtree/rollback_segtree_beats.hpp"
#line 1 "beats_acted_monoid/concept.hpp"
#line 5 "beats_acted_monoid/concept.hpp"
#line 7 "beats_acted_monoid/concept.hpp"
namespace m1une {
namespace beats_acted_monoid {
// An acted monoid whose action may require descent before it can be applied.
template <typename AM>
concept IsBeatsActedMonoid = m1une::acted_monoid::IsActedMonoid<AM> &&
requires(typename AM::value_type x, typename AM::operator_type f) {
{ AM::can_apply(f, x) } -> std::same_as<bool>;
};
} // namespace beats_acted_monoid
} // namespace m1une
#line 12 "ds/segtree/rollback_segtree_beats.hpp"
namespace m1une {
namespace ds {
// Generic Segment Tree Beats for actions that may require recursive descent.
template <m1une::beats_acted_monoid::IsBeatsActedMonoid ActedMonoid>
struct RollbackSegtreeBeats {
using value_type = typename ActedMonoid::value_type;
using operator_type = typename ActedMonoid::operator_type;
using T = value_type;
using F = operator_type;
private:
int _n = 0;
int _size = 1;
struct Node {
T value = ActedMonoid::id();
F lazy = ActedMonoid::op_id();
bool has_lazy = false;
};
detail::RollbackJournal<Node> _journal;
static T mapping_at(const F& f, const T& value, long long ordinal) {
if constexpr (requires(F g, T x, long long i) {
ActedMonoid::mapping(g, x, i);
}) {
return ActedMonoid::mapping(f, value, ordinal);
} else {
return ActedMonoid::mapping(f, value);
}
}
static bool can_apply_at(const F& f, const T& value, long long ordinal) {
if constexpr (requires(F g, T x, long long i) {
ActedMonoid::can_apply(g, x, i);
}) {
return ActedMonoid::can_apply(f, value, ordinal);
} else {
return ActedMonoid::can_apply(f, value);
}
}
static F shift_operator(const F& f, long long ordinal) {
if constexpr (requires(F g, long long i) {
ActedMonoid::op_shift(g, i);
}) {
return ActedMonoid::op_shift(f, ordinal);
} else {
return f;
}
}
void initialize(std::vector<T>&& values) {
_journal.clear();
_n = int(values.size());
_size = int(m1une::math::bit_ceil((unsigned int)_n));
_journal.nodes.assign(2 * _size, Node());
_journal.saved_epoch.assign(_journal.nodes.size(), 0);
for (int i = 0; i < _n; ++i) {
_journal[_size + i].value = std::move(values[i]);
}
for (int k = _size - 1; k >= 1; --k) update(k);
}
void update(int node) {
_journal.touch(node);
_journal[node].value = ActedMonoid::op(
_journal[node * 2].value,
_journal[node * 2 + 1].value
);
}
void all_apply(int node, int left, int right, const F& f) {
if (_n <= left) return;
if (can_apply_at(f, _journal[node].value, 0)) {
_journal.touch(node);
_journal[node].value = mapping_at(f, _journal[node].value, 0);
if (node < _size) {
_journal[node].lazy = ActedMonoid::op_comp(f, _journal[node].lazy);
_journal[node].has_lazy = true;
}
return;
}
assert(right - left > 1);
push(node, left, right);
int middle = left + (right - left) / 2;
all_apply(node * 2, left, middle, f);
all_apply(
node * 2 + 1,
middle,
right,
shift_operator(f, middle - left)
);
update(node);
}
void push(int node, int left, int right) {
assert(right - left > 1);
if (!_journal[node].has_lazy) return;
int middle = left + (right - left) / 2;
F f = _journal[node].lazy;
_journal.touch(node);
_journal[node].lazy = ActedMonoid::op_id();
_journal[node].has_lazy = false;
all_apply(node * 2, left, middle, f);
all_apply(
node * 2 + 1,
middle,
right,
shift_operator(f, middle - left)
);
}
void set_impl(
int node,
int left,
int right,
int index,
T value
) {
if (right - left == 1) {
_journal.touch(node);
_journal[node].value = std::move(value);
return;
}
push(node, left, right);
int middle = left + (right - left) / 2;
if (index < middle) {
set_impl(node * 2, left, middle, index, std::move(value));
} else {
set_impl(
node * 2 + 1,
middle,
right,
index,
std::move(value)
);
}
update(node);
}
T get_impl(int node, int left, int right, int index) {
if (right - left == 1) return _journal[node].value;
push(node, left, right);
int middle = left + (right - left) / 2;
if (index < middle) {
return get_impl(node * 2, left, middle, index);
}
return get_impl(node * 2 + 1, middle, right, index);
}
T prod_impl(
int node,
int left,
int right,
int query_left,
int query_right
) {
if (
query_right <= left || right <= query_left || _n <= left
) {
return ActedMonoid::id();
}
if (query_left <= left && right <= query_right) {
return _journal[node].value;
}
push(node, left, right);
int middle = left + (right - left) / 2;
return ActedMonoid::op(
prod_impl(
node * 2,
left,
middle,
query_left,
query_right
),
prod_impl(
node * 2 + 1,
middle,
right,
query_left,
query_right
)
);
}
void apply_impl(
int node,
int left,
int right,
int query_left,
int query_right,
int base_left,
const F& f
) {
if (
query_right <= left || right <= query_left || _n <= left
) {
return;
}
if (query_left <= left && right <= query_right) {
all_apply(
node,
left,
right,
shift_operator(f, left - base_left)
);
return;
}
push(node, left, right);
int middle = left + (right - left) / 2;
apply_impl(
node * 2,
left,
middle,
query_left,
query_right,
base_left,
f
);
apply_impl(
node * 2 + 1,
middle,
right,
query_left,
query_right,
base_left,
f
);
update(node);
}
void collect_impl(
int node,
int left,
int right,
int query_left,
int query_right,
std::vector<T>& result
) {
if (
query_right <= left || right <= query_left || _n <= left
) {
return;
}
if (right - left == 1) {
result.push_back(_journal[node].value);
return;
}
push(node, left, right);
int middle = left + (right - left) / 2;
collect_impl(
node * 2,
left,
middle,
query_left,
query_right,
result
);
collect_impl(
node * 2 + 1,
middle,
right,
query_left,
query_right,
result
);
}
template <class Predicate>
bool max_right_impl(
int node,
int left,
int right,
int query_left,
Predicate& predicate,
T& product,
int& answer
) {
if (right <= query_left || _n <= left) return true;
if (query_left <= left) {
T next = ActedMonoid::op(product, _journal[node].value);
if (predicate(next)) {
product = std::move(next);
return true;
}
if (right - left == 1) {
answer = left;
return false;
}
}
push(node, left, right);
int middle = left + (right - left) / 2;
if (!max_right_impl(
node * 2,
left,
middle,
query_left,
predicate,
product,
answer
)) {
return false;
}
return max_right_impl(
node * 2 + 1,
middle,
right,
query_left,
predicate,
product,
answer
);
}
template <class Predicate>
bool min_left_impl(
int node,
int left,
int right,
int query_right,
Predicate& predicate,
T& product,
int& answer
) {
if (query_right <= left || _n <= left) return true;
if (right <= query_right) {
T next = ActedMonoid::op(_journal[node].value, product);
if (predicate(next)) {
product = std::move(next);
return true;
}
if (right - left == 1) {
answer = right;
return false;
}
}
push(node, left, right);
int middle = left + (right - left) / 2;
if (!min_left_impl(
node * 2 + 1,
middle,
right,
query_right,
predicate,
product,
answer
)) {
return false;
}
return min_left_impl(
node * 2,
left,
middle,
query_right,
predicate,
product,
answer
);
}
public:
RollbackSegtreeBeats() {
initialize({});
}
explicit RollbackSegtreeBeats(int n) {
assert(0 <= n);
initialize(std::vector<T>(n, ActedMonoid::id()));
}
explicit RollbackSegtreeBeats(const std::vector<T>& values) {
initialize(std::vector<T>(values));
}
explicit RollbackSegtreeBeats(std::vector<T>&& values) {
initialize(std::move(values));
}
template <typename U>
requires (!std::same_as<U, T>) && (
requires(U x) { ActedMonoid::make(x); } ||
requires(U x, int i) { ActedMonoid::make(x, i); } ||
std::convertible_to<U, T>
)
explicit RollbackSegtreeBeats(const std::vector<U>& values) {
std::vector<T> converted;
converted.reserve(values.size());
for (int i = 0; i < int(values.size()); ++i) {
if constexpr (requires(U x) { ActedMonoid::make(x); }) {
converted.push_back(ActedMonoid::make(values[i]));
} else if constexpr (requires(U x, int index) {
ActedMonoid::make(x, index);
}) {
converted.push_back(ActedMonoid::make(values[i], i));
} else {
converted.push_back(static_cast<T>(values[i]));
}
}
initialize(std::move(converted));
}
int size() const {
return _n;
}
bool empty() const {
return _n == 0;
}
std::size_t node_count() const { return _journal.nodes.size(); }
void set(int index, T value) {
assert(0 <= index && index < _n);
set_impl(1, 0, _size, index, std::move(value));
}
void set_inplace(int index, T value) { set(index, std::move(value)); }
T get(int index) {
assert(0 <= index && index < _n);
return get_impl(1, 0, _size, index);
}
T operator[](int index) {
return get(index);
}
T prod(int left, int right) {
assert(0 <= left && left <= right && right <= _n);
if (left == right) return ActedMonoid::id();
return prod_impl(1, 0, _size, left, right);
}
T all_prod() const {
return _journal[1].value;
}
void apply(int index, F f) {
assert(0 <= index && index < _n);
apply_impl(1, 0, _size, index, index + 1, index, f);
}
void apply(int left, int right, F f) {
assert(0 <= left && left <= right && right <= _n);
if (left == right) return;
apply_impl(1, 0, _size, left, right, left, f);
}
void apply_inplace(int index, F f) { apply(index, std::move(f)); }
void apply_inplace(int left, int right, F f) {
apply(left, right, std::move(f));
}
std::vector<T> to_vector() {
return to_vector(0, _n);
}
std::vector<T> to_vector(int left, int right) {
assert(0 <= left && left <= right && right <= _n);
std::vector<T> result;
result.reserve(right - left);
collect_impl(1, 0, _size, left, right, result);
return result;
}
template <class Predicate>
int max_right(int left, Predicate predicate) {
assert(0 <= left && left <= _n);
assert(predicate(ActedMonoid::id()));
if (left == _n) return _n;
T product = ActedMonoid::id();
int answer = _n;
max_right_impl(
1,
0,
_size,
left,
predicate,
product,
answer
);
return answer;
}
template <class Predicate>
int min_left(int right, Predicate predicate) {
assert(0 <= right && right <= _n);
assert(predicate(ActedMonoid::id()));
if (right == 0) return 0;
T product = ActedMonoid::id();
int answer = 0;
min_left_impl(
1,
0,
_size,
right,
predicate,
product,
answer
);
return answer;
}
int snapshot() { return _journal.snapshot(); }
int snapshot_count() const { return _journal.snapshot_count(); }
void reserve_snapshots(int count) { _journal.reserve_snapshots(count); }
void rollback(int state) { _journal.rollback(state); }
void clear_history() { _journal.clear_history(); }
void release() { initialize({}); }
};
} // namespace ds
} // namespace m1une
#line 1 "ds/stack/rollback_stack.hpp"
#line 8 "ds/stack/rollback_stack.hpp"
namespace m1une {
namespace ds {
template <class T>
struct RollbackStack {
private:
enum class Kind { push, pop, clear };
struct Entry {
Kind kind;
std::optional<T> value;
std::vector<T> values;
};
std::vector<T> _values;
std::vector<Entry> _history;
std::vector<std::size_t> _checkpoints;
std::size_t _stored_values = 0;
public:
RollbackStack() = default;
int size() const { return int(_values.size()); }
bool empty() const { return _values.empty(); }
std::size_t node_count() const { return _stored_values; }
const T& top() const {
assert(!empty());
return _values.back();
}
void push(T value) {
if (!_checkpoints.empty()) _history.push_back(Entry{Kind::push, std::nullopt, {}});
_values.push_back(std::move(value));
++_stored_values;
}
template <class... Args>
void emplace(Args&&... args) {
if (!_checkpoints.empty()) _history.push_back(Entry{Kind::push, std::nullopt, {}});
_values.emplace_back(std::forward<Args>(args)...);
++_stored_values;
}
void pop() {
assert(!empty());
if (_checkpoints.empty()) {
_values.pop_back();
--_stored_values;
} else {
Entry entry{Kind::pop, std::nullopt, {}};
entry.value.emplace(std::move(_values.back()));
_values.pop_back();
_history.push_back(std::move(entry));
}
}
void clear() {
if (_checkpoints.empty()) {
_stored_values -= _values.size();
_values.clear();
} else {
Entry entry{Kind::clear, std::nullopt, {}};
entry.values = std::move(_values);
_values.clear();
_history.push_back(std::move(entry));
}
}
int snapshot() {
_checkpoints.push_back(_history.size());
return int(_checkpoints.size());
}
int snapshot_count() const { return int(_checkpoints.size()); }
void reserve_snapshots(int count) {
assert(0 <= count);
_checkpoints.reserve(count);
}
private:
void restore_one() {
Entry entry = std::move(_history.back());
_history.pop_back();
if (entry.kind == Kind::push) {
_values.pop_back();
--_stored_values;
} else if (entry.kind == Kind::pop) {
_values.push_back(std::move(*entry.value));
} else {
_values = std::move(entry.values);
}
}
public:
void rollback(int state) {
assert(1 <= state && state <= snapshot_count());
while (_history.size() > _checkpoints[state - 1]) restore_one();
_checkpoints.resize(state);
}
void clear_history() {
for (const Entry& entry : _history) {
if (entry.value) --_stored_values;
_stored_values -= entry.values.size();
}
_history.clear();
_checkpoints.clear();
}
void release() {
_values.clear();
_history.clear();
_checkpoints.clear();
_stored_values = 0;
}
};
} // namespace ds
} // namespace m1une
#line 19 "verify/ds/rollback_counterparts.test.cpp"
#line 22 "verify/ds/rollback_counterparts.test.cpp"
#include <iostream>
#include <random>
#line 25 "verify/ds/rollback_counterparts.test.cpp"
#line 1 "acted_monoid/range_add_range_sum.hpp"
namespace m1une {
namespace acted_monoid {
template <typename T>
struct RangeAddRangeSumNode {
T sum;
long long size;
};
template <typename T>
struct RangeAddRangeSum {
using value_type = RangeAddRangeSumNode<T>;
using operator_type = T;
static constexpr bool commutative = true;
static constexpr bool operator_commutative = true;
// Value Monoid (Sum)
static constexpr value_type id() {
return {T(0), 0};
}
static constexpr value_type op(const value_type& a, const value_type& b) {
return {a.sum + b.sum, a.size + b.size};
}
static constexpr value_type inv(const value_type& x) {
return {-x.sum, -x.size};
}
// Operator Monoid (Add)
static constexpr operator_type op_id() {
return 0;
}
static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
return f + g;
}
// Mapping (sum + f * size)
static constexpr value_type mapping(const operator_type& f, const value_type& x) {
return {x.sum + f * x.size, x.size};
}
// Helper for initializing a leaf node
static constexpr value_type make(const T& val) {
return {val, 1};
}
};
} // namespace acted_monoid
} // namespace m1une
#line 1 "beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp"
#line 8 "beats_acted_monoid/range_chmin_chmax_add_range_sum.hpp"
namespace m1une {
namespace beats_acted_monoid {
template <std::signed_integral T>
struct RangeChminChmaxAddRangeSumNode {
T sum;
T maximum;
T second_maximum;
T minimum;
T second_minimum;
int maximum_count;
int minimum_count;
int length;
};
// Beats acted monoid for range chmin/chmax/add updates and range sum queries.
template <std::signed_integral T = long long>
struct RangeChminChmaxAddRangeSum {
using value_type = RangeChminChmaxAddRangeSumNode<T>;
// Represents f(x) = clamp(x + add, lower, upper).
struct operator_type {
T add;
T lower;
T upper;
};
static constexpr bool commutative = true;
static constexpr bool operator_commutative = false;
static constexpr T negative_infinity = std::numeric_limits<T>::lowest();
static constexpr T positive_infinity = std::numeric_limits<T>::max();
private:
static constexpr T shift_lower_bound(T bound, T add) {
return bound == negative_infinity ? bound : bound + add;
}
static constexpr T shift_upper_bound(T bound, T add) {
return bound == positive_infinity ? bound : bound + add;
}
static constexpr void apply_add(value_type& value, T add) {
if (value.length == 0 || add == T(0)) return;
value.sum += add * T(value.length);
value.maximum += add;
value.minimum += add;
if (value.maximum_count != value.length) {
value.second_maximum += add;
}
if (value.minimum_count != value.length) {
value.second_minimum += add;
}
}
static constexpr bool can_apply_chmin(
const value_type& value,
T upper
) {
return value.maximum <= upper ||
value.maximum_count == value.length ||
value.second_maximum < upper;
}
static constexpr void apply_chmin(value_type& value, T upper) {
if (value.maximum <= upper) return;
assert(can_apply_chmin(value, upper));
value.sum +=
(upper - value.maximum) * T(value.maximum_count);
if (value.minimum == value.maximum) {
value.minimum = upper;
} else if (value.second_minimum == value.maximum) {
value.second_minimum = upper;
}
value.maximum = upper;
}
static constexpr bool can_apply_chmax(
const value_type& value,
T lower
) {
return lower <= value.minimum ||
value.minimum_count == value.length ||
lower < value.second_minimum;
}
static constexpr void apply_chmax(value_type& value, T lower) {
if (lower <= value.minimum) return;
assert(can_apply_chmax(value, lower));
value.sum +=
(lower - value.minimum) * T(value.minimum_count);
if (value.maximum == value.minimum) {
value.maximum = lower;
} else if (value.second_maximum == value.minimum) {
value.second_maximum = lower;
}
value.minimum = lower;
}
static constexpr value_type constant_value(T value, int length) {
return {
value * T(length),
value,
negative_infinity,
value,
positive_infinity,
length,
length,
length
};
}
public:
static constexpr value_type id() {
return {
T(0),
negative_infinity,
negative_infinity,
positive_infinity,
positive_infinity,
0,
0,
0
};
}
static constexpr value_type op(
const value_type& left,
const value_type& right
) {
if (left.length == 0) return right;
if (right.length == 0) return left;
value_type result;
result.sum = left.sum + right.sum;
result.length = left.length + right.length;
result.maximum = std::max(left.maximum, right.maximum);
result.maximum_count = 0;
result.second_maximum = negative_infinity;
if (left.maximum == result.maximum) {
result.maximum_count += left.maximum_count;
result.second_maximum = std::max(
result.second_maximum,
left.second_maximum
);
} else {
result.second_maximum = std::max(
result.second_maximum,
left.maximum
);
}
if (right.maximum == result.maximum) {
result.maximum_count += right.maximum_count;
result.second_maximum = std::max(
result.second_maximum,
right.second_maximum
);
} else {
result.second_maximum = std::max(
result.second_maximum,
right.maximum
);
}
result.minimum = std::min(left.minimum, right.minimum);
result.minimum_count = 0;
result.second_minimum = positive_infinity;
if (left.minimum == result.minimum) {
result.minimum_count += left.minimum_count;
result.second_minimum = std::min(
result.second_minimum,
left.second_minimum
);
} else {
result.second_minimum = std::min(
result.second_minimum,
left.minimum
);
}
if (right.minimum == result.minimum) {
result.minimum_count += right.minimum_count;
result.second_minimum = std::min(
result.second_minimum,
right.second_minimum
);
} else {
result.second_minimum = std::min(
result.second_minimum,
right.minimum
);
}
return result;
}
static constexpr operator_type op_id() {
return {T(0), negative_infinity, positive_infinity};
}
// Returns f(g(x)).
static constexpr operator_type op_comp(
const operator_type& f,
const operator_type& g
) {
T lower = shift_lower_bound(g.lower, f.add);
T upper = shift_upper_bound(g.upper, f.add);
return {
g.add + f.add,
std::clamp(lower, f.lower, f.upper),
std::clamp(upper, f.lower, f.upper)
};
}
static constexpr bool can_apply(
const operator_type& f,
const value_type& value
) {
if (value.length == 0 || f.lower == f.upper) return true;
value_type mapped = value;
apply_add(mapped, f.add);
if (
mapped.maximum <= f.lower ||
f.upper <= mapped.minimum
) {
return true;
}
if (!can_apply_chmax(mapped, f.lower)) return false;
apply_chmax(mapped, f.lower);
return can_apply_chmin(mapped, f.upper);
}
static constexpr value_type mapping(
const operator_type& f,
const value_type& value
) {
assert(can_apply(f, value));
if (value.length == 0) return value;
if (f.lower == f.upper) {
return constant_value(f.lower, value.length);
}
value_type result = value;
apply_add(result, f.add);
if (result.maximum <= f.lower) {
return constant_value(f.lower, result.length);
}
if (f.upper <= result.minimum) {
return constant_value(f.upper, result.length);
}
apply_chmax(result, f.lower);
apply_chmin(result, f.upper);
return result;
}
static constexpr value_type make(const T& value) {
return constant_value(value, 1);
}
static constexpr operator_type make_chmin(const T& upper) {
return {T(0), negative_infinity, upper};
}
static constexpr operator_type make_chmax(const T& lower) {
return {T(0), lower, positive_infinity};
}
static constexpr operator_type make_add(const T& add) {
return {add, negative_infinity, positive_infinity};
}
};
} // namespace beats_acted_monoid
} // namespace m1une
#line 1 "monoid/add.hpp"
namespace m1une {
namespace monoid {
// Monoid for addition (Range Sum).
template <typename T>
struct Add {
using value_type = T;
static constexpr bool commutative = true;
// Returns the identity element for addition, which is 0.
static constexpr T id() {
return T(0);
}
// Returns the sum of a and b.
static constexpr T op(const T& a, const T& b) {
return a + b;
}
static constexpr T inv(const T& x) {
return -x;
}
};
} // namespace monoid
} // namespace m1une
#line 29 "verify/ds/rollback_counterparts.test.cpp"
namespace {
using Add = m1une::monoid::Add<long long>;
using RangeAddSum = m1une::acted_monoid::RangeAddRangeSum<long long>;
void assert_lazy_array(
m1une::ds::RollbackDynamicLazyMonoidArray<RangeAddSum>& array,
const std::vector<long long>& expected
) {
std::vector<RangeAddSum::value_type> values = array.to_vector();
assert(values.size() == expected.size());
for (int index = 0; index < int(values.size()); ++index) {
assert(values[index].sum == expected[index]);
assert(values[index].size == 1);
}
}
void test_sequence_containers() {
m1une::ds::RollbackStack<int> stack;
stack.push(1);
int outer = stack.snapshot();
stack.emplace(2);
int inner = stack.snapshot();
stack.push(3);
stack.rollback(inner);
assert(stack.top() == 2 && stack.snapshot_count() == inner);
stack.pop();
stack.rollback(outer);
assert(stack.top() == 1 && stack.snapshot_count() == outer);
stack.push(4);
stack.rollback(outer);
assert(stack.top() == 1);
m1une::ds::RollbackQueue<int> queue;
queue.push(1);
outer = queue.snapshot();
queue.push_back(2);
queue.pop_front();
assert(queue.front() == 2);
queue.rollback(outer);
assert(queue.front() == 1 && queue.back() == 1);
m1une::ds::RollbackDeque<int> deque;
deque.push_back(2);
outer = deque.snapshot();
deque.emplace_front(1);
deque.emplace_back(3);
deque.pop_front();
assert(deque.front() == 2 && deque.back() == 3);
deque.rollback(outer);
assert(deque.front() == 2 && deque.back() == 2);
}
void test_ordered_containers() {
m1une::ds::RollbackOrderedSet<int> set({2, 1});
int outer = set.snapshot();
assert(set.insert(3));
assert(!set.insert(3));
assert(set.erase(1));
int inner = set.snapshot();
set.clear();
set.rollback(inner);
assert(set.to_vector() == std::vector<int>({2, 3}));
set.rollback(outer);
assert(set.to_vector() == std::vector<int>({1, 2}));
m1une::ds::RollbackOrderedMultiset<int> multiset({2, 2, 3});
outer = multiset.snapshot();
assert(multiset.erase_one(2));
multiset.insert(1, 3);
assert(multiset.erase_all(3) == 1);
assert(multiset.count(1) == 3 && multiset.count(2) == 1);
multiset.rollback(outer);
assert(multiset.to_vector() == std::vector<int>({2, 2, 3}));
}
void test_dynamic_arrays() {
m1une::ds::RollbackDynamicArray<int> array(std::vector<int>{1, 2, 3});
int outer = array.snapshot();
array.insert(1, 5);
array.reverse(0, 4);
array.erase(1, 3);
assert(array.to_vector() == std::vector<int>({3, 1}));
array.rollback(outer);
assert(array.to_vector() == std::vector<int>({1, 2, 3}));
m1une::ds::RollbackDynamicMonoidArray<Add> monoid_array(
std::vector<long long>{1, 2, 3}
);
outer = monoid_array.snapshot();
monoid_array.set(1, 7);
monoid_array.push_back(4);
assert(monoid_array.all_prod() == 15);
monoid_array.rollback(outer);
assert(monoid_array.to_vector() == std::vector<long long>({1, 2, 3}));
m1une::ds::RollbackDynamicLazyMonoidArray<RangeAddSum> lazy_array(
std::vector<long long>{1, 2, 3, 4}
);
outer = lazy_array.snapshot();
lazy_array.apply(0, 3, 4);
lazy_array.reverse(1, 4);
lazy_array.insert(2, RangeAddSum::make(10));
lazy_array.erase(0);
assert(lazy_array.all_prod().sum == 27);
int inner = lazy_array.snapshot();
lazy_array.clear();
assert(lazy_array.empty());
lazy_array.rollback(inner);
assert(lazy_array.all_prod().sum == 27);
lazy_array.rollback(outer);
std::vector<RangeAddSum::value_type> restored = lazy_array.to_vector();
assert(restored.size() == 4);
for (int index = 0; index < 4; ++index) {
assert(restored[index].sum == index + 1);
assert(restored[index].size == 1);
}
}
void randomized_lazy_array_test() {
std::mt19937 random(0);
std::vector<long long> naive = {0, 1, 2, 3, 4, 5};
m1une::ds::RollbackDynamicLazyMonoidArray<RangeAddSum> array(naive);
for (int round = 0; round < 80; ++round) {
int state = array.snapshot();
std::vector<long long> saved = naive;
for (int step = 0; step < 35; ++step) {
int type = int(random() % 5);
if (type == 0 && !naive.empty()) {
int pos = int(random() % naive.size());
long long value = int(random() % 31) - 15;
array.set(pos, RangeAddSum::make(value));
naive[pos] = value;
} else if (type == 1) {
int left = int(random() % (naive.size() + 1));
int right = left + int(random() % (naive.size() - left + 1));
long long add = int(random() % 11) - 5;
array.apply(left, right, add);
for (int index = left; index < right; ++index) naive[index] += add;
} else if (type == 2) {
int left = int(random() % (naive.size() + 1));
int right = left + int(random() % (naive.size() - left + 1));
array.reverse(left, right);
std::reverse(naive.begin() + left, naive.begin() + right);
} else if (type == 3) {
int pos = int(random() % (naive.size() + 1));
std::vector<long long> raw_values = {
int(random() % 21) - 10,
int(random() % 21) - 10
};
std::vector<RangeAddSum::value_type> values;
for (long long value : raw_values) {
values.push_back(RangeAddSum::make(value));
}
array.insert(pos, std::move(values));
naive.insert(
naive.begin() + pos, raw_values.begin(), raw_values.end()
);
} else if (!naive.empty()) {
int pos = int(random() % naive.size());
array.erase(pos);
naive.erase(naive.begin() + pos);
}
assert_lazy_array(array, naive);
}
array.rollback(state);
naive = std::move(saved);
assert_lazy_array(array, naive);
array.clear_history();
}
}
void test_segment_trees() {
m1une::ds::RollbackSegtree<Add> seg(std::vector<long long>{1, 2, 3, 4});
int outer = seg.snapshot();
seg.set(1, 10);
seg.set(1, 12);
assert(seg.all_prod() == 20);
int inner = seg.snapshot();
seg.set(0, 8);
seg.rollback(inner);
assert(seg.all_prod() == 20);
seg.rollback(outer);
assert(seg.all_prod() == 10);
m1une::ds::RollbackLazySegtree<RangeAddSum> lazy(
std::vector<long long>{1, 2, 3, 4}
);
outer = lazy.snapshot();
lazy.apply(1, 4, 5);
lazy.set(0, RangeAddSum::make(9));
assert(lazy.all_prod().sum == 33);
assert(lazy.prod(1, 3).sum == 15);
lazy.rollback(outer);
assert(lazy.all_prod().sum == 10);
m1une::ds::RollbackDualSegtree<Add> dual(4);
outer = dual.snapshot();
dual.apply(0, 3, 4);
dual.set(1, 2);
assert(dual.get(0) == 4 && dual.get(1) == 2);
dual.rollback(outer);
assert(dual.get(0) == 0 && dual.get(1) == 0);
m1une::ds::RollbackDynamicSegtree<Add> dynamic(-10, 10);
outer = dynamic.snapshot();
dynamic.set(-4, 7);
dynamic.set(8, 3);
assert(dynamic.all_prod() == 10);
dynamic.rollback(outer);
assert(dynamic.all_prod() == 0 && dynamic.node_count() == 0);
m1une::ds::RollbackDynamicLazySegtree<RangeAddSum> dynamic_lazy(
-10, 10, RangeAddSum::id()
);
outer = dynamic_lazy.snapshot();
dynamic_lazy.set(-2, RangeAddSum::make(3));
dynamic_lazy.apply(-3, 2, 4);
assert(dynamic_lazy.get(-2).sum == 7);
assert(dynamic_lazy.prod(-3, 2).sum == 7);
dynamic_lazy.rollback(outer);
assert(dynamic_lazy.get(-2).sum == 0 && dynamic_lazy.node_count() == 0);
m1une::ds::RollbackDynamicDualSegtree<Add> dynamic_dual(-10, 10, 0);
outer = dynamic_dual.snapshot();
dynamic_dual.apply(-3, 5, 7);
dynamic_dual.set(0, 2);
assert(dynamic_dual.get(-1) == 7 && dynamic_dual.get(0) == 2);
dynamic_dual.rollback(outer);
assert(dynamic_dual.get(-1) == 0 && dynamic_dual.get(0) == 0);
using Beats = m1une::beats_acted_monoid::RangeChminChmaxAddRangeSum<long long>;
m1une::ds::RollbackSegtreeBeats<Beats> beats(
std::vector<long long>{1, 5, 3, 7}
);
outer = beats.snapshot();
Beats::operator_type chmin;
chmin.add = 0;
chmin.lower = Beats::negative_infinity;
chmin.upper = 4;
beats.apply(0, 4, chmin);
assert(beats.all_prod().sum == 12);
assert(beats.prod(1, 4).sum == 11);
beats.rollback(outer);
assert(beats.all_prod().sum == 16);
}
void randomized_segment_tree_test() {
using Beats = m1une::beats_acted_monoid::RangeChminChmaxAddRangeSum<long long>;
std::mt19937 random(1);
constexpr int size = 24;
std::vector<long long> naive(size);
std::vector<long long> lazy_naive(size);
m1une::ds::RollbackLazySegtree<RangeAddSum> lazy(lazy_naive);
m1une::ds::RollbackSegtreeBeats<Beats> beats(naive);
for (int round = 0; round < 70; ++round) {
int lazy_state = lazy.snapshot();
int beats_state = beats.snapshot();
std::vector<long long> saved = naive;
std::vector<long long> lazy_saved = lazy_naive;
for (int step = 0; step < 45; ++step) {
int type = int(random() % 3);
int left = int(random() % size);
int right = left + 1 + int(random() % (size - left));
if (type == 0) {
long long add = int(random() % 17) - 8;
lazy.apply(left, right, add);
Beats::operator_type action;
action.add = add;
action.lower = Beats::negative_infinity;
action.upper = Beats::positive_infinity;
beats.apply(left, right, action);
for (int index = left; index < right; ++index) naive[index] += add;
for (int index = left; index < right; ++index) lazy_naive[index] += add;
} else if (type == 1) {
long long value = int(random() % 41) - 20;
lazy.set(left, RangeAddSum::make(value));
beats.set(left, Beats::make(value));
naive[left] = value;
lazy_naive[left] = value;
} else {
long long upper = int(random() % 31) - 15;
Beats::operator_type action;
action.add = 0;
action.lower = Beats::negative_infinity;
action.upper = upper;
beats.apply(left, right, action);
for (int index = left; index < right; ++index) {
naive[index] = std::min(naive[index], upper);
}
}
long long sum = 0;
for (long long value : naive) sum += value;
assert(beats.all_prod().sum == sum);
long long lazy_sum = 0;
for (long long value : lazy_naive) lazy_sum += value;
assert(lazy.all_prod().sum == lazy_sum);
}
beats.rollback(beats_state);
lazy.rollback(lazy_state);
naive = std::move(saved);
lazy_naive = std::move(lazy_saved);
long long sum = 0;
for (long long value : naive) sum += value;
assert(beats.all_prod().sum == sum);
long long lazy_sum = 0;
for (long long value : lazy_naive) lazy_sum += value;
assert(lazy.all_prod().sum == lazy_sum);
beats.clear_history();
lazy.clear_history();
}
}
void test_potentialized_dsu() {
m1une::ds::RollbackPotentializedDsu<Add> dsu(5);
assert(dsu.merge(0, 1, 3));
int outer = dsu.snapshot();
assert(dsu.merge(1, 2, 4));
assert(dsu.diff(0, 2) == 7);
assert(!dsu.merge(0, 2, 8));
int inner = dsu.snapshot();
assert(dsu.merge(3, 4, -2));
dsu.rollback(inner);
assert(!dsu.same(3, 4));
dsu.rollback(outer);
assert(!dsu.same(0, 2));
assert(dsu.diff(0, 1) == 3);
assert(dsu.component_count() == 4);
}
} // namespace
int main() {
test_sequence_containers();
test_ordered_containers();
test_dynamic_arrays();
randomized_lazy_array_test();
test_segment_trees();
randomized_segment_tree_test();
test_potentialized_dsu();
long long first, second;
std::cin >> first >> second;
std::cout << first + second << '\n';
}
verify/ds/rollback_counterparts.test.cpp