src/algebra/system/monoid.hpp

• View this file on GitHub
• Last update: 2020-11-26 16:42:40+09:00
• Include: #include "src/algebra/system/monoid.hpp"

Required by

• Segment Tree (src/data_structure/segment_tree/basic.hpp)
• Lazy Segment Tree (src/data_structure/segment_tree/lazy.hpp)

Verified with

• test/aizu-online-judge/2450.test.cpp
• test/aizu-online-judge/DSL_2_A.test.cpp
• test/library-checker/point_add_range_sum.test.cpp
• test/library-checker/point_set_range_composite.test.cpp
• test/library-checker/range_affine_range_sum.test.cpp
• test/library-checker/static_range_inversions_query.test.cpp

Code

#pragma once
#include <limits>

namespace workspace {
template <class T, class E = T> struct min_monoid {
  using value_type = T;
  static T min, max;
  T value;
  min_monoid() : value(max) {}
  min_monoid(const T &value) : value(value) {}
  operator T() const { return value; }
  min_monoid operator+(const min_monoid &rhs) const {
    return value < rhs.value ? *this : rhs;
  }
  min_monoid operator*(const E &rhs) const;
};

template <class T, class E>
T min_monoid<T, E>::min = std::numeric_limits<T>::min() / 2;
template <class T, class E>
T min_monoid<T, E>::max = std::numeric_limits<T>::max() / 2;

template <class T, class E = T> struct max_monoid : min_monoid<T, E> {
  using base = min_monoid<T, E>;
  using base::min_monoid;
  max_monoid() : base(base::min) {}
  max_monoid operator+(const max_monoid &rhs) const {
    return !(base::value < rhs.value) ? *this : rhs;
  }
  max_monoid operator*(const E &rhs) const;
};
}

#line 2 "src/algebra/system/monoid.hpp"
#include <limits>

namespace workspace {
template <class T, class E = T> struct min_monoid {
  using value_type = T;
  static T min, max;
  T value;
  min_monoid() : value(max) {}
  min_monoid(const T &value) : value(value) {}
  operator T() const { return value; }
  min_monoid operator+(const min_monoid &rhs) const {
    return value < rhs.value ? *this : rhs;
  }
  min_monoid operator*(const E &rhs) const;
};

template <class T, class E>
T min_monoid<T, E>::min = std::numeric_limits<T>::min() / 2;
template <class T, class E>
T min_monoid<T, E>::max = std::numeric_limits<T>::max() / 2;

template <class T, class E = T> struct max_monoid : min_monoid<T, E> {
  using base = min_monoid<T, E>;
  using base::min_monoid;
  max_monoid() : base(base::min) {}
  max_monoid operator+(const max_monoid &rhs) const {
    return !(base::value < rhs.value) ? *this : rhs;
  }
  max_monoid operator*(const E &rhs) const;
};
}

Back to top page