verify/acted_monoid/range_bitwise_and_or_xor_range_sum.test.cpp

• View this file on GitHub
• Last update: 2026-08-12 00:05:48+09:00
• Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

• Acted Monoid Concept (acted_monoid/concept.hpp)
• Acted Monoid Concept (acted_monoid/concept.hpp)
• Range Bitwise AND/OR/XOR Range Sum (acted_monoid/range_bitwise_and_or_xor_range_sum.hpp)
• Lazy Segment Tree (ds/segtree/lazy_segtree.hpp)
• Bit Ceil (math/bit_ceil.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

#include "../../acted_monoid/concept.hpp"
#include "../../acted_monoid/range_bitwise_and_or_xor_range_sum.hpp"
#include "../../ds/segtree/lazy_segtree.hpp"

namespace {

using AM = m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<long long, 10>;
using SignedFullWidth = m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<long long, 63>;
using UnsignedFullWidth =
    m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<unsigned long long, 64>;

long long apply_scalar(const AM::operator_type& f, long long x) {
    return (x & f.and_mask) ^ f.xor_mask;
}

void test_composition() {
    std::vector<AM::operator_type> operators;
    for (long long mask = 0; mask < 32; ++mask) {
        operators.push_back(AM::make_and(mask));
        operators.push_back(AM::make_or(mask));
        operators.push_back(AM::make_xor(mask));
    }

    for (const auto& f : operators) {
        for (const auto& g : operators) {
            auto composition = AM::op_comp(f, g);
            for (long long x = 0; x < 32; ++x) {
                assert(apply_scalar(composition, x) == apply_scalar(f, apply_scalar(g, x)));
            }
        }
    }
}

void test_randomized() {
    constexpr int n = 73;
    constexpr long long mask = (1LL << 10) - 1;
    std::uint64_t state = 123456789;
    auto random = [&state]() {
        state ^= state << 7;
        state ^= state >> 9;
        return state;
    };

    std::vector<long long> values(n);
    for (long long& value : values) value = static_cast<long long>(random() & mask);
    m1une::ds::LazySegtree<AM> seg(values);

    for (int step = 0; step < 5000; ++step) {
        int l = static_cast<int>(random() % (n + 1));
        int r = static_cast<int>(random() % (n + 1));
        if (r < l) std::swap(l, r);

        if (random() % 4 != 0) {
            long long operand = static_cast<long long>(random() & mask);
            int type = static_cast<int>(random() % 3);
            AM::operator_type f = AM::op_id();
            if (type == 0) {
                f = AM::make_and(operand);
                for (int i = l; i < r; ++i) values[i] &= operand;
            } else if (type == 1) {
                f = AM::make_or(operand);
                for (int i = l; i < r; ++i) values[i] |= operand;
            } else {
                f = AM::make_xor(operand);
                for (int i = l; i < r; ++i) values[i] ^= operand;
            }
            seg.apply(l, r, f);
        } else {
            long long expected = 0;
            for (int i = l; i < r; ++i) expected += values[i];
            assert(seg.prod(l, r).sum == expected);
        }

        int index = static_cast<int>(random() % n);
        assert(seg.get(index).sum == values[index]);
    }
}

static_assert(m1une::acted_monoid::IsActedMonoid<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';
}

#line 1 "verify/acted_monoid/range_bitwise_and_or_xor_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 "acted_monoid/concept.hpp"



#include <concepts>

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 "acted_monoid/range_bitwise_and_or_xor_range_sum.hpp"



#include <array>
#line 6 "acted_monoid/range_bitwise_and_or_xor_range_sum.hpp"
#include <type_traits>

namespace m1une {
namespace acted_monoid {

template <typename T, int BITS>
struct RangeBitwiseAndOrXorRangeSumNode {
    T sum;
    std::array<long long, BITS> bit_count;
    long long size;
};

// Acted monoid for range bitwise AND, OR, and XOR updates and range sum queries.
template <typename T, int BITS = 30>
struct RangeBitwiseAndOrXorRangeSum {
    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 = RangeBitwiseAndOrXorRangeSumNode<T, BITS>;

    // Represents f(x) = (x & and_mask) ^ xor_mask on the lowest BITS bits.
    struct operator_type {
        T and_mask;
        T xor_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() {
        value_type res;
        res.sum = T(0);
        res.bit_count.fill(0);
        res.size = 0;
        return res;
    }

    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res;
        res.sum = a.sum + b.sum;
        res.size = a.size + b.size;
        for (int i = 0; i < BITS; ++i) {
            res.bit_count[i] = a.bit_count[i] + b.bit_count[i];
        }
        return res;
    }

    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, (g.xor_mask & f.and_mask) ^ f.xor_mask};
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        value_type res = x;
        res.sum = T(0);
        for (int i = 0; i < BITS; ++i) {
            long long count = ((f.and_mask >> i) & T(1)) ? x.bit_count[i] : 0;
            if ((f.xor_mask >> i) & T(1)) count = x.size - count;
            res.bit_count[i] = count;
            res.sum += static_cast<T>(count) * (T(1) << i);
        }
        return res;
    }

    static constexpr value_type make(const T& value) {
        value_type res;
        res.sum = value;
        res.size = 1;
        for (int i = 0; i < BITS; ++i) {
            res.bit_count[i] = (value >> i) & T(1);
        }
        return res;
    }

    static constexpr operator_type make_and(const T& mask) {
        return {mask & bit_mask(), T(0)};
    }

    static constexpr operator_type make_or(const T& mask) {
        T normalized = mask & bit_mask();
        return {bit_mask() ^ normalized, normalized};
    }

    static constexpr operator_type make_xor(const T& mask) {
        return {bit_mask(), mask & bit_mask()};
    }
};

}  // namespace acted_monoid
}  // namespace m1une


#line 1 "ds/segtree/lazy_segtree.hpp"



#include <bit>
#line 7 "ds/segtree/lazy_segtree.hpp"
#include <utility>
#line 9 "ds/segtree/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 12 "ds/segtree/lazy_segtree.hpp"

namespace m1une {
namespace ds {

// A highly generic Lazy Segment Tree utilizing C++20 Concepts for type safety.
// It operates on any Acted Monoid structure satisfying the `m1une::acted_monoid::IsActedMonoid` concept.
template <m1une::acted_monoid::IsActedMonoid ActedMonoid>
struct LazySegtree {
    using T = typename ActedMonoid::value_type;
    using F = typename ActedMonoid::operator_type;

   private:
    int _n, _size, _log;
    std::vector<T> _d;
    std::vector<F> _lz;

    // Recalculates the value of the node k from its children.
    void update(int k) {
        _d[k] = ActedMonoid::op(_d[2 * k], _d[2 * k + 1]);
    }

    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;
        }
    }

    int node_length(int k) const {
        int level = std::bit_width((unsigned int)k) - 1;
        return _size >> level;
    }

    int node_left(int k) const {
        int level = std::bit_width((unsigned int)k) - 1;
        int len = _size >> level;
        return (k - (1 << level)) * len;
    }

    // Applies the operator f to the node k and updates its lazy tag if it's an internal node.
    void all_apply(int k, F f) {
        _d[k] = mapping_at(f, _d[k], 0);
        if (k < _size) {
            _lz[k] = ActedMonoid::op_comp(f, _lz[k]);
        }
    }

    // Propagates the lazy tag of the node k down to its children.
    void push(int k) {
        all_apply(2 * k, _lz[k]);
        all_apply(2 * k + 1, shift_operator(_lz[k], node_length(k) / 2));
        _lz[k] = ActedMonoid::op_id();
    }

   public:
    // Constructs an empty lazy segment tree.
    LazySegtree() : LazySegtree(0) {}

    // Constructs a lazy segment tree of size `n`, initialized with the identity element.
    explicit LazySegtree(int n) : LazySegtree(std::vector<T>(n, ActedMonoid::id())) {}

    // Constructs a lazy segment tree from an existing vector.
    explicit LazySegtree(const std::vector<T>& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, ActedMonoid::id());
        _lz.assign(_size, ActedMonoid::op_id());
        for (int i = 0; i < _n; i++) _d[_size + i] = v[i];
        for (int i = _size - 1; i >= 1; i--) update(i);
    }
    explicit LazySegtree(std::vector<T>&& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, ActedMonoid::id());
        _lz.assign(_size, ActedMonoid::op_id());
        for (int i = 0; i < _n; i++) _d[_size + i] = std::move(v[i]);
        for (int i = _size - 1; i >= 1; i--) update(i);
    }

    // Constructs a lazy segment tree from a vector of a different type U.
    // It automatically adapts to the Monoid's initialization requirements:
    // 1. ActedMonoid::make(val) if it exists.
    // 2. ActedMonoid::make(val, index) if the monoid requires global indices.
    // 3. static_cast<T>(val) as a fallback for simple monoids.
    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 LazySegtree(const std::vector<U>& v) : _n(int(v.size())) {
        _size = m1une::math::bit_ceil((unsigned int)(_n));
        _log = 0;
        while ((1U << _log) < (unsigned int)(_size)) _log++;
        _d.assign(2 * _size, ActedMonoid::id());
        _lz.assign(_size, ActedMonoid::op_id());
        for (int i = 0; i < _n; i++) {
            if constexpr (requires(U x) { ActedMonoid::make(x); }) {
                _d[_size + i] = ActedMonoid::make(v[i]);
            } else if constexpr (requires(U x, int idx) { ActedMonoid::make(x, idx); }) {
                _d[_size + i] = ActedMonoid::make(v[i], i);
            } else {
                _d[_size + i] = static_cast<T>(v[i]);
            }
        }
        for (int i = _size - 1; i >= 1; i--) update(i);
    }

    // Returns the number of elements.
    int size() const {
        return _n;
    }

    // Returns whether the tree is empty.
    bool empty() const {
        return _n == 0;
    }

    // Assigns x to the p-th element.
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _d[p] = x;
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    // Returns the value of the p-th element.
    T get(int p) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        return _d[p];
    }

    // Returns the value of the p-th element.
    T operator[](int p) {
        return get(p);
    }

    // Returns the product (result of the monoid operation) in the range [l, r).
    T prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return ActedMonoid::id();

        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        T sml = ActedMonoid::id(), smr = ActedMonoid::id();
        while (l < r) {
            if (l & 1) sml = ActedMonoid::op(sml, _d[l++]);
            if (r & 1) smr = ActedMonoid::op(_d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return ActedMonoid::op(sml, smr);
    }

    // Returns the product of the entire array.
    T all_prod() const {
        return _d[1];
    }

    // Returns all elements as a vector.
    std::vector<T> to_vector() {
        for (int k = 1; k < _size; k++) push(k);
        std::vector<T> res;
        res.reserve(_n);
        for (int i = 0; i < _n; i++) res.push_back(_d[_size + i]);
        return res;
    }

    // Returns the elements in the range [l, r) as a vector.
    std::vector<T> to_vector(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        std::vector<T> res;
        res.reserve(r - l);
        for (int i = l; i < r; i++) res.push_back(get(i));
        return res;
    }

    // Applies the operator f to the p-th element.
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += _size;
        for (int i = _log; i >= 1; i--) push(p >> i);
        _d[p] = mapping_at(f, _d[p], 0);
        for (int i = 1; i <= _log; i++) update(p >> i);
    }

    // Applies the operator f to all elements in the range [l, r).
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        int base_l = l;
        l += _size;
        r += _size;

        for (int i = _log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) {
                    all_apply(l, shift_operator(f, node_left(l) - base_l));
                    l++;
                }
                if (r & 1) {
                    --r;
                    all_apply(r, shift_operator(f, node_left(r) - base_l));
                }
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= _log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    // Finds the largest r such that g(prod(l, r)) is true.
    template <class F_pred>
    int max_right(int l, F_pred g) {
        assert(0 <= l && l <= _n);
        assert(g(ActedMonoid::id()));
        if (l == _n) return _n;
        l += _size;
        for (int i = _log; i >= 1; i--) push(l >> i);
        T sm = ActedMonoid::id();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(ActedMonoid::op(sm, _d[l]))) {
                while (l < _size) {
                    push(l);
                    l = (2 * l);
                    if (g(ActedMonoid::op(sm, _d[l]))) {
                        sm = ActedMonoid::op(sm, _d[l]);
                        l++;
                    }
                }
                return l - _size;
            }
            sm = ActedMonoid::op(sm, _d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    // Finds the smallest l such that g(prod(l, r)) is true.
    template <class F_pred>
    int min_left(int r, F_pred g) {
        assert(0 <= r && r <= _n);
        assert(g(ActedMonoid::id()));
        if (r == 0) return 0;
        r += _size;
        for (int i = _log; i >= 1; i--) push((r - 1) >> i);
        T sm = ActedMonoid::id();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(ActedMonoid::op(_d[r], sm))) {
                while (r < _size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(ActedMonoid::op(_d[r], sm))) {
                        sm = ActedMonoid::op(_d[r], sm);
                        r--;
                    }
                }
                return r + 1 - _size;
            }
            sm = ActedMonoid::op(_d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

}  // namespace ds
}  // namespace m1une


#line 13 "verify/acted_monoid/range_bitwise_and_or_xor_range_sum.test.cpp"

namespace {

using AM = m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<long long, 10>;
using SignedFullWidth = m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<long long, 63>;
using UnsignedFullWidth =
    m1une::acted_monoid::RangeBitwiseAndOrXorRangeSum<unsigned long long, 64>;

long long apply_scalar(const AM::operator_type& f, long long x) {
    return (x & f.and_mask) ^ f.xor_mask;
}

void test_composition() {
    std::vector<AM::operator_type> operators;
    for (long long mask = 0; mask < 32; ++mask) {
        operators.push_back(AM::make_and(mask));
        operators.push_back(AM::make_or(mask));
        operators.push_back(AM::make_xor(mask));
    }

    for (const auto& f : operators) {
        for (const auto& g : operators) {
            auto composition = AM::op_comp(f, g);
            for (long long x = 0; x < 32; ++x) {
                assert(apply_scalar(composition, x) == apply_scalar(f, apply_scalar(g, x)));
            }
        }
    }
}

void test_randomized() {
    constexpr int n = 73;
    constexpr long long mask = (1LL << 10) - 1;
    std::uint64_t state = 123456789;
    auto random = [&state]() {
        state ^= state << 7;
        state ^= state >> 9;
        return state;
    };

    std::vector<long long> values(n);
    for (long long& value : values) value = static_cast<long long>(random() & mask);
    m1une::ds::LazySegtree<AM> seg(values);

    for (int step = 0; step < 5000; ++step) {
        int l = static_cast<int>(random() % (n + 1));
        int r = static_cast<int>(random() % (n + 1));
        if (r < l) std::swap(l, r);

        if (random() % 4 != 0) {
            long long operand = static_cast<long long>(random() & mask);
            int type = static_cast<int>(random() % 3);
            AM::operator_type f = AM::op_id();
            if (type == 0) {
                f = AM::make_and(operand);
                for (int i = l; i < r; ++i) values[i] &= operand;
            } else if (type == 1) {
                f = AM::make_or(operand);
                for (int i = l; i < r; ++i) values[i] |= operand;
            } else {
                f = AM::make_xor(operand);
                for (int i = l; i < r; ++i) values[i] ^= operand;
            }
            seg.apply(l, r, f);
        } else {
            long long expected = 0;
            for (int i = l; i < r; ++i) expected += values[i];
            assert(seg.prod(l, r).sum == expected);
        }

        int index = static_cast<int>(random() % n);
        assert(seg.get(index).sum == values[index]);
    }
}

static_assert(m1une::acted_monoid::IsActedMonoid<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';
}

Back to top page