#line 1 "verify/beats_acted_monoid/range_bitwise_and_or_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>
#line 1 "beats_acted_monoid/concept.hpp"
#include <concepts>
#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 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 1 "beats_acted_monoid/range_bitwise_and_or_range_sum.hpp"
#line 6 "beats_acted_monoid/range_bitwise_and_or_range_sum.hpp"
#include <type_traits>
namespace m1une {
namespace beats_acted_monoid {
template <typename T>
struct RangeBitwiseAndOrRangeSumNode {
T sum;
T bitwise_and;
T bitwise_or;
long long length;
};
// Beats acted monoid for range bitwise AND/OR updates and range sum queries.
template <typename T, int BITS = 30>
struct RangeBitwiseAndOrRangeSum {
static_assert(
std::is_integral_v<T> &&
!std::is_same_v<std::remove_cv_t<T>, bool>
);
static_assert(0 < BITS && BITS <= std::numeric_limits<T>::digits);
using value_type = RangeBitwiseAndOrRangeSumNode<T>;
// Represents f(x) = (x & and_mask) | or_mask.
struct operator_type {
T and_mask;
T or_mask;
};
static constexpr bool commutative = true;
static constexpr bool operator_commutative = false;
static constexpr T bit_mask() {
if constexpr (
std::is_unsigned_v<T> &&
BITS == std::numeric_limits<T>::digits
) {
return ~T(0);
} else {
return
(T(1) << (BITS - 1)) |
((T(1) << (BITS - 1)) - 1);
}
}
static constexpr value_type id() {
return {T(0), bit_mask(), T(0), 0};
}
static constexpr value_type op(
const value_type& left,
const value_type& right
) {
return {
left.sum + right.sum,
left.bitwise_and & right.bitwise_and,
left.bitwise_or | right.bitwise_or,
left.length + right.length
};
}
static constexpr operator_type op_id() {
return {bit_mask(), T(0)};
}
// Returns f(g(x)).
static constexpr operator_type op_comp(
const operator_type& f,
const operator_type& g
) {
return {
(f.and_mask & g.and_mask) & bit_mask(),
((g.or_mask & f.and_mask) | f.or_mask) & bit_mask()
};
}
static constexpr bool can_apply(
const operator_type& f,
const value_type& value
) {
if (value.length == 0) return true;
T changed = ((~f.and_mask) | f.or_mask) & bit_mask();
T mixed = value.bitwise_and ^ value.bitwise_or;
return (changed & mixed) == T(0);
}
static constexpr value_type mapping(
const operator_type& f,
const value_type& value
) {
assert(can_apply(f, value));
if (value.length == 0) return value;
T changed = ((~f.and_mask) | f.or_mask) & bit_mask();
T old_uniform = value.bitwise_and & changed;
T new_uniform =
((old_uniform & f.and_mask) | f.or_mask) & changed;
value_type result = value;
result.sum +=
(new_uniform - old_uniform) * T(value.length);
result.bitwise_and =
((value.bitwise_and & f.and_mask) | f.or_mask) & bit_mask();
result.bitwise_or =
((value.bitwise_or & f.and_mask) | f.or_mask) & bit_mask();
return result;
}
static constexpr value_type make(const T& value) {
assert((value & ~bit_mask()) == T(0));
return {value, value, value, 1};
}
static constexpr operator_type make_and(const T& mask) {
return {mask & bit_mask(), T(0)};
}
static constexpr operator_type make_or(const T& mask) {
return {bit_mask(), mask & bit_mask()};
}
};
} // namespace beats_acted_monoid
} // namespace m1une
#line 1 "ds/segtree/segtree_beats.hpp"
#line 6 "ds/segtree/segtree_beats.hpp"
#include <utility>
#line 8 "ds/segtree/segtree_beats.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 11 "ds/segtree/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 SegtreeBeats {
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;
std::vector<T> _data;
std::vector<F> _lazy;
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) {
_n = int(values.size());
_size = int(m1une::math::bit_ceil((unsigned int)_n));
_data.assign(2 * _size, ActedMonoid::id());
_lazy.assign(_size, ActedMonoid::op_id());
for (int i = 0; i < _n; ++i) {
_data[_size + i] = std::move(values[i]);
}
for (int k = _size - 1; k >= 1; --k) update(k);
}
void update(int node) {
_data[node] = ActedMonoid::op(
_data[node * 2],
_data[node * 2 + 1]
);
}
void all_apply(int node, int left, int right, const F& f) {
if (_n <= left) return;
if (can_apply_at(f, _data[node], 0)) {
_data[node] = mapping_at(f, _data[node], 0);
if (node < _size) {
_lazy[node] = ActedMonoid::op_comp(f, _lazy[node]);
}
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);
int middle = left + (right - left) / 2;
F f = _lazy[node];
_lazy[node] = ActedMonoid::op_id();
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) {
_data[node] = 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 _data[node];
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 _data[node];
}
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(_data[node]);
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, _data[node]);
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(_data[node], 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:
SegtreeBeats() {
initialize({});
}
explicit SegtreeBeats(int n) {
assert(0 <= n);
initialize(std::vector<T>(n, ActedMonoid::id()));
}
explicit SegtreeBeats(const std::vector<T>& values) {
initialize(std::vector<T>(values));
}
explicit SegtreeBeats(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 SegtreeBeats(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;
}
void set(int index, T value) {
assert(0 <= index && index < _n);
set_impl(1, 0, _size, 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 _data[1];
}
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);
}
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;
}
};
} // namespace ds
} // namespace m1une
#line 13 "verify/beats_acted_monoid/range_bitwise_and_or_range_sum.test.cpp"
namespace {
using AM =
m1une::beats_acted_monoid::RangeBitwiseAndOrRangeSum<long long, 10>;
using SignedFullWidth =
m1une::beats_acted_monoid::RangeBitwiseAndOrRangeSum<long long, 63>;
using UnsignedFullWidth =
m1une::beats_acted_monoid::RangeBitwiseAndOrRangeSum<
unsigned long long,
64
>;
long long apply_scalar(const AM::operator_type& f, long long value) {
return (value & f.and_mask) | f.or_mask;
}
void test_composition() {
std::vector<AM::operator_type> operators;
for (long long mask = 0; mask < 32; ++mask) {
operators.emplace_back(AM::make_and(mask));
operators.emplace_back(AM::make_or(mask));
}
for (const auto& f : operators) {
for (const auto& g : operators) {
auto composition = AM::op_comp(f, g);
for (long long value = 0; value < 32; ++value) {
assert(
apply_scalar(composition, value) ==
apply_scalar(f, apply_scalar(g, value))
);
}
}
}
}
void test_randomized() {
constexpr int size = 73;
constexpr long long mask = (1LL << 10) - 1;
std::uint64_t state = 0x3141592653589793ULL;
auto random = [&state]() {
state ^= state << 7;
state ^= state >> 9;
return state;
};
std::vector<long long> values(size);
for (long long& value : values) {
value = static_cast<long long>(random() & mask);
}
m1une::ds::SegtreeBeats<AM> seg(values);
for (int step = 0; step < 10000; ++step) {
int left = int(random() % (size + 1));
int right = int(random() % (size + 1));
if (right < left) std::swap(left, right);
if (random() % 3 != 0) {
long long operand = static_cast<long long>(random() & mask);
if (random() & 1) {
seg.apply(left, right, AM::make_and(operand));
for (int index = left; index < right; ++index) {
values[index] &= operand;
}
} else {
seg.apply(left, right, AM::make_or(operand));
for (int index = left; index < right; ++index) {
values[index] |= operand;
}
}
} else {
long long expected = 0;
for (int index = left; index < right; ++index) {
expected += values[index];
}
assert(seg.prod(left, right).sum == expected);
}
int index = int(random() % size);
assert(seg.get(index).sum == values[index]);
}
}
static_assert(m1une::beats_acted_monoid::IsBeatsActedMonoid<AM>);
static_assert(AM::commutative);
static_assert(!AM::operator_commutative);
static_assert(
SignedFullWidth::bit_mask() ==
std::numeric_limits<long long>::max()
);
static_assert(
UnsignedFullWidth::bit_mask() ==
std::numeric_limits<unsigned long long>::max()
);
} // namespace
int main() {
test_composition();
test_randomized();
long long a, b;
std::cin >> a >> b;
std::cout << a + b << '\n';
}
verify/beats_acted_monoid/range_bitwise_and_or_range_sum.test.cpp