Longest Same Monoid
(monoid/longest_same.hpp)

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

Overview

A monoid for finding the maximum length of a contiguous subarray where all elements have the same value.

Initialization

When initializing a segment tree from an array of elements, you should use the make helper method to correctly build the leaf nodes.

Example

#include "ds/segtree/segtree.hpp"
#include "monoid/longest_same.hpp"
#include <iostream>
#include <vector>

using LSM = m1une::monoid::LongestSame<long long>;

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

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

    m1une::ds::Segtree<LSM> seg(init_data);

    // Get the maximum length of consecutive identical elements in range [0, 7)
    auto res = seg.prod(0, N);
    std::cout << "Max Length: " << res.max_len << "\n"; // Output: 3 (because of "5, 5, 5")

    return 0;
}

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_LONGEST_SAME_HPP
#define M1UNE_MONOID_LONGEST_SAME_HPP 1

#include <algorithm>

namespace m1une {
namespace monoid {

template <typename T>
struct LongestSameNode {
    int len;
    int max_len;
    T l_val;
    int l_len;
    T r_val;
    int r_len;
};

// Monoid for finding the maximum length of a contiguous subarray
// where all elements have the same value.
template <typename T>
struct LongestSame {
    using value_type = LongestSameNode<T>;
    static constexpr bool commutative = false;

    // The identity element represents an empty array.
    static constexpr value_type id() {
        return {0, 0, T(), 0, T(), 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);

        if (a.r_val == b.l_val) {
            res.max_len = std::max(res.max_len, a.r_len + b.l_len);
        }

        res.l_val = a.l_val;
        res.l_len = a.l_len;
        if (a.len == a.l_len && a.l_val == b.l_val) {
            res.l_len += b.l_len;
        }

        res.r_val = b.r_val;
        res.r_len = b.r_len;
        if (b.len == b.r_len && b.r_val == a.r_val) {
            res.r_len += a.r_len;
        }

        return res;
    }

    // Helper to securely create a leaf node from a single value.
    static constexpr value_type make(const T& val) {
        return {1, 1, val, 1, val, 1};
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_LONGEST_SAME_HPP

#line 1 "monoid/longest_same.hpp"



#include <algorithm>

namespace m1une {
namespace monoid {

template <typename T>
struct LongestSameNode {
    int len;
    int max_len;
    T l_val;
    int l_len;
    T r_val;
    int r_len;
};

// Monoid for finding the maximum length of a contiguous subarray
// where all elements have the same value.
template <typename T>
struct LongestSame {
    using value_type = LongestSameNode<T>;
    static constexpr bool commutative = false;

    // The identity element represents an empty array.
    static constexpr value_type id() {
        return {0, 0, T(), 0, T(), 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);

        if (a.r_val == b.l_val) {
            res.max_len = std::max(res.max_len, a.r_len + b.l_len);
        }

        res.l_val = a.l_val;
        res.l_len = a.l_len;
        if (a.len == a.l_len && a.l_val == b.l_val) {
            res.l_len += b.l_len;
        }

        res.r_val = b.r_val;
        res.r_len = b.r_len;
        if (b.len == b.r_len && b.r_val == a.r_val) {
            res.r_len += a.r_len;
        }

        return res;
    }

    // Helper to securely create a leaf node from a single value.
    static constexpr value_type make(const T& val) {
        return {1, 1, val, 1, val, 1};
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page