m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Range Affine Range Min Max
(acted_monoid/range_affine_range_min_max.hpp)

Overview

An acted monoid that tracks the minimum and maximum values of a range while supporting affine transformations $f(x) = ax + b$.

Negative scale factors reverse the ordering, so the mapping swaps the roles of the previous minimum and maximum before applying the transformation.

Template Parameters

Data Structure

Element Creation

When building or updating individual elements, use the make(val) helper function to encapsulate the scalar into a node matching the value monoid specification.

static constexpr value_type make(const T& val)

Example

#include "ds/segtree/lazy_segtree.hpp"
#include "acted_monoid/range_affine_range_min_max.hpp"
#include <iostream>
#include <vector>

using AM = m1une::acted_monoid::RangeAffineRangeMinMax<long long>;

int main() {
    std::vector<long long> A = {2, 5, 3, 8, 4};
    int N = A.size();

    std::vector<AM::value_type> init_nodes(N);
    for (int i = 0; i < N; ++i) {
        init_nodes[i] = AM::make(A[i]);
    }

    m1une::ds::LazySegtree<AM> seg(init_nodes);

    // Query range [0, 3) -> Elements: {2, 5, 3} -> Min: 2, Max: 5
    auto q1 = seg.prod(0, 3);
    std::cout << "Min: " << q1.min_val << ", Max: " << q1.max_val << "\n"; // Output: Min: 2, Max: 5

    // Apply negative affine transformation f(x) = -2x + 3 to range [0, 3)
    // New values inside range become:
    // 2 -> -2(2) + 3 = -1
    // 5 -> -2(5) + 3 = -7
    // 3 -> -2(3) + 3 = -3
    // Range is now: {-1, -7, -3}
    seg.apply(0, 3, {-2, 3});

    // Query range [0, 3) again -> Min should be -7, Max should be -1
    auto q2 = seg.prod(0, 3);
    std::cout << "Updated Min: " << q2.min_val << ", Updated Max: " << q2.max_val << "\n"; // Output: Min: -7, Max: -1

    return 0;
}

Interface and Complexity

This is a stateless acted-monoid tag. Lazy data structures use its public value_type, operator_type, id(), op(a, b), op_id(), op_comp(f, g), and mapping(f, x) members. Helpers such as make(...), shifted mappings, or reversal-aware mappings are described above when the header provides them.

The static operations are $O(1)$ for the scalar metadata stored by these range acted monoids, aside from the cost of the underlying arithmetic type.

Verified with

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_AFFINE_RANGE_MIN_MAX_HPP
#define M1UNE_ACTED_MONOID_RANGE_AFFINE_RANGE_MIN_MAX_HPP 1

#include <algorithm>
#include <limits>
#include <utility>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAffineRangeMinMaxNode {
    T min_val;
    T max_val;
};

template <typename T, T MinId = std::numeric_limits<T>::max(), T MaxId = std::numeric_limits<T>::lowest()>
struct RangeAffineRangeMinMax {
    using value_type = RangeAffineRangeMinMaxNode<T>;
    using operator_type = std::pair<T, T>;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    static constexpr value_type id() {
        return {MinId, MaxId};
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {std::min(a.min_val, b.min_val), std::max(a.max_val, b.max_val)};
    }

    static constexpr operator_type op_id() {
        return {T(1), T(0)};
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return {f.first * g.first, f.first * g.second + f.second};
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.min_val == MinId) return x;

        T v1 = f.first * x.min_val + f.second;
        T v2 = f.first * x.max_val + f.second;

        if (f.first < 0) {
            return {v2, v1};
        }
        return {v1, v2};
    }

    static constexpr value_type make(const T& val) {
        return {val, val};
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_AFFINE_RANGE_MIN_MAX_HPP
#line 1 "acted_monoid/range_affine_range_min_max.hpp"



#include <algorithm>
#include <limits>
#include <utility>

namespace m1une {
namespace acted_monoid {

template <typename T>
struct RangeAffineRangeMinMaxNode {
    T min_val;
    T max_val;
};

template <typename T, T MinId = std::numeric_limits<T>::max(), T MaxId = std::numeric_limits<T>::lowest()>
struct RangeAffineRangeMinMax {
    using value_type = RangeAffineRangeMinMaxNode<T>;
    using operator_type = std::pair<T, T>;
    static constexpr bool commutative = true;
    static constexpr bool operator_commutative = false;

    static constexpr value_type id() {
        return {MinId, MaxId};
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return {std::min(a.min_val, b.min_val), std::max(a.max_val, b.max_val)};
    }

    static constexpr operator_type op_id() {
        return {T(1), T(0)};
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return {f.first * g.first, f.first * g.second + f.second};
    }

    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (x.min_val == MinId) return x;

        T v1 = f.first * x.min_val + f.second;
        T v2 = f.first * x.max_val + f.second;

        if (f.first < 0) {
            return {v2, v1};
        }
        return {v1, v2};
    }

    static constexpr value_type make(const T& val) {
        return {val, val};
    }
};

}  // namespace acted_monoid
}  // namespace m1une
Back to top page