Max contiguous monoid
(Mylib/AlgebraicStructure/Monoid/max_contiguous.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

• id()
  • 長さ0の列を表す。
  • return (0, 0, 0, 0)
• op(a, b)
  • aの右隣にbを隣接させる。

Requirements

Notes

• 連続する1の最大長を管理する。
  • value_type = (最大連続長, 左側最大連続長, 右側最大連続長, セグメント長)

Problems

• Codeforces Round #276 (Div. 1) E. Sign on Fence

References

Code

#pragma once
#include <algorithm>
#include <tuple>

namespace haar_lib {
  namespace max_contiguous_monoid_impl {
    struct internal_value {
      int count, left, right, length;
      internal_value() {}
      internal_value(int count, int left, int right, int length) : count(count), left(left), right(right), length(length) {}
      internal_value(int x) : count(x ? 1 : 0), left(x ? 1 : 0), right(x ? 1 : 0), length(1) {}
    };
  }  // namespace max_contiguous_monoid_impl

  struct max_contiguous_monoid {
    using value_type = max_contiguous_monoid_impl::internal_value;

    value_type operator()() const {
      return {0, 0, 0, 0};
    }

    value_type operator()(const value_type &a, const value_type &b) const {
      return {
          std::max({a.count, b.count, a.right + b.left}),
          a.count == a.length ? a.count + b.left : a.left,
          b.count == b.length ? b.count + a.right : b.right,
          a.length + b.length};
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/AlgebraicStructure/Monoid/max_contiguous.cpp"
#include <algorithm>
#include <tuple>

namespace haar_lib {
  namespace max_contiguous_monoid_impl {
    struct internal_value {
      int count, left, right, length;
      internal_value() {}
      internal_value(int count, int left, int right, int length) : count(count), left(left), right(right), length(length) {}
      internal_value(int x) : count(x ? 1 : 0), left(x ? 1 : 0), right(x ? 1 : 0), length(1) {}
    };
  }  // namespace max_contiguous_monoid_impl

  struct max_contiguous_monoid {
    using value_type = max_contiguous_monoid_impl::internal_value;

    value_type operator()() const {
      return {0, 0, 0, 0};
    }

    value_type operator()(const value_type &a, const value_type &b) const {
      return {
          std::max({a.count, b.count, a.right + b.left}),
          a.count == a.length ? a.count + b.left : a.left,
          b.count == b.length ? b.count + a.right : b.right,
          a.length + b.length};
    }
  };
}  // namespace haar_lib

Back to top page