Range Update Range Longest True
(acted_monoid/range_update_range_longest_true.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "acted_monoid/range_update_range_longest_true.hpp"

Overview

An Acted Monoid designed to solve “Hotel Queries” or contiguous memory allocation problems. It supports range overwrite operations (setting a block to all true or all false) and queries the maximum contiguous length of true values in a range.

Because updating an entire segment to true simply makes the contiguous length equal to the segment’s total length (and updating to false makes it 0), the mapping operation executes in $O(1)$ time by leveraging the m1une::monoid::LongestTrueNode.

Data Structure

• using value_type = m1une::monoid::LongestTrueNode; The state maintained in each segment tree node:
  • len: Total length of the segment.
  • max_len: The longest contiguous block of true.
  • l_len: The length of the contiguous true block starting from the left edge.
  • r_len: The length of the contiguous true block starting from the right edge.
• using operator_type = std::optional<bool>; An optional boolean representing the overwrite operation. std::nullopt represents the identity operation.

Example

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

using AM = m1une::acted_monoid::RangeUpdateRangeLongestTrue;

int main() {
    // 1 implies the seat is empty (true), 0 implies occupied (false)
    std::vector<bool> A = {true, false, true, true, false, true};
    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);

    // Initial longest block of empty seats is 2 (indices 2 to 3)
    std::cout << "Max empty block: " << seg.all_prod().max_len << "\n"; // Output: 2

    // Free up seats in range [4, 6) -> {true, false, true, true, true, true}
    seg.apply(4, 6, std::optional<bool>(true));

    // The new longest contiguous block of empty seats is now 4 (indices 2 to 5)
    std::cout << "Max empty block: " << seg.all_prod().max_len << "\n"; // Output: 4

    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.

Depends on

• Longest True Monoid (monoid/longest_true.hpp)

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_LONGEST_TRUE_HPP
#define M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_LONGEST_TRUE_HPP 1

#include <optional>

#include "../monoid/longest_true.hpp"

namespace m1une {
namespace acted_monoid {

struct RangeUpdateRangeLongestTrue {
    using BaseMonoid = m1une::monoid::LongestTrue;
    using value_type = typename BaseMonoid::value_type;
    using operator_type = std::optional<bool>;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = false;

    // Value Monoid
    static constexpr value_type id() {
        return BaseMonoid::id();
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return BaseMonoid::op(a, b);
    }

    // Operator Monoid (Update/Overwrite)
    static constexpr operator_type op_id() {
        return std::nullopt;
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f.has_value() ? f : g;
    }

    // Mapping
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f.has_value()) return x;
        bool v = f.value();

        // If updating to 'true', the entire length satisfies the condition.
        // If updating to 'false', zero elements satisfy the condition.
        return {x.len, v ? x.len : 0, v ? x.len : 0, v ? x.len : 0};
    }

    // Helper for initializing a leaf node
    static constexpr value_type make(bool val) {
        return BaseMonoid::make(val);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

#endif  // M1UNE_ACTED_MONOID_RANGE_UPDATE_RANGE_LONGEST_TRUE_HPP

#line 1 "acted_monoid/range_update_range_longest_true.hpp"



#include <optional>

#line 1 "monoid/longest_true.hpp"



#include <algorithm>

namespace m1une {
namespace monoid {

struct LongestTrueNode {
    int len;
    int max_len;
    int l_len;
    int r_len;
};

// Monoid for finding the maximum length of a contiguous subarray
// where all elements satisfy a certain condition (i.e., are "true").
struct LongestTrue {
    using value_type = LongestTrueNode;
    static constexpr bool commutative = false;

    // The identity element represents an empty array.
    static constexpr value_type id() {
        return {0, 0, 0, 0};
    }

    // Merges two segments.
    static constexpr value_type op(const value_type& a, const value_type& b) {
        if (a.len == 0) return b;
        if (b.len == 0) return a;

        value_type res;
        res.len = a.len + b.len;
        res.max_len = std::max({a.max_len, b.max_len, a.r_len + b.l_len});

        res.l_len = a.l_len;
        if (a.len == a.l_len) res.l_len += b.l_len;

        res.r_len = b.r_len;
        if (b.len == b.r_len) res.r_len += a.r_len;

        return res;
    }

    // Helper to securely create a leaf node from a boolean condition.
    static constexpr value_type make(bool val) {
        return {1, val ? 1 : 0, val ? 1 : 0, val ? 1 : 0};
    }
};

}  // namespace monoid
}  // namespace m1une


#line 7 "acted_monoid/range_update_range_longest_true.hpp"

namespace m1une {
namespace acted_monoid {

struct RangeUpdateRangeLongestTrue {
    using BaseMonoid = m1une::monoid::LongestTrue;
    using value_type = typename BaseMonoid::value_type;
    using operator_type = std::optional<bool>;
    static constexpr bool commutative = false;
    static constexpr bool operator_commutative = false;

    // Value Monoid
    static constexpr value_type id() {
        return BaseMonoid::id();
    }
    static constexpr value_type op(const value_type& a, const value_type& b) {
        return BaseMonoid::op(a, b);
    }

    // Operator Monoid (Update/Overwrite)
    static constexpr operator_type op_id() {
        return std::nullopt;
    }
    static constexpr operator_type op_comp(const operator_type& f, const operator_type& g) {
        return f.has_value() ? f : g;
    }

    // Mapping
    static constexpr value_type mapping(const operator_type& f, const value_type& x) {
        if (!f.has_value()) return x;
        bool v = f.value();

        // If updating to 'true', the entire length satisfies the condition.
        // If updating to 'false', zero elements satisfy the condition.
        return {x.len, v ? x.len : 0, v ? x.len : 0, v ? x.len : 0};
    }

    // Helper for initializing a leaf node
    static constexpr value_type make(bool val) {
        return BaseMonoid::make(val);
    }
};

}  // namespace acted_monoid
}  // namespace m1une

Back to top page