src/data-structure/segment-tree/presets/monoid/combined-structure-add-maximum.hpp

View this file on GitHub
Last update: 2023-05-03 14:59:16+09:00
Include: #include "src/data-structure/segment-tree/presets/monoid/combined-structure-add-maximum.hpp"

Depends on

Required by

区間加算 + 区間最大クエリ solver (Range Add Range Maximum Query Solver) (src/data-structure/segment-tree/presets/range-add-range-maximum-query-solver.hpp)

Verified with

test/aoj/dsl_2_h/range-maximum.test.cpp

Code

#pragma once

#include "src/data-structure/segment-tree/presets/monoid/operator-structure-add.hpp"
#include "src/data-structure/segment-tree/presets/monoid/value-structure-maximum.hpp"

namespace luz::monoid {

  template < typename T >
  class RangeAddRangeMaximumQueryMonoid {
    using V  = RangeMaximumQueryMonoid< T >;
    using VT = typename V::value_type;
    using O  = RangeAddQueryMonoid< T >;
    using OT = typename O::value_type;

   public:
    using value_structure    = V;
    using operator_structure = O;

    static constexpr T operation(VT a, OT b) {
      return a + b;
    }
  };

} // namespace luz::monoid

#line 2 "src/data-structure/segment-tree/presets/monoid/combined-structure-add-maximum.hpp"

#line 2 "src/data-structure/segment-tree/presets/monoid/operator-structure-add.hpp"

namespace luz::monoid {

  template < typename T >
  class RangeAddQueryMonoid {

   public:
    using value_type = T;

    static constexpr T operation(T a, T b) {
      return a + b;
    }

    static constexpr T identity() {
      return T();
    }
  };

} // namespace luz::monoid
#line 2 "src/data-structure/segment-tree/presets/monoid/value-structure-maximum.hpp"

#include <algorithm>
#include <limits>

namespace luz::monoid {

  template < typename T >
  class RangeMaximumQueryMonoid {

    static constexpr T identity_{std::numeric_limits< T >::min()};

   public:
    using value_type = T;

    static constexpr T operation(T a, T b) {
      return std::max(a, b);
    }

    static constexpr T identity() {
      return identity_;
    }
  };

} // namespace luz::monoid
#line 5 "src/data-structure/segment-tree/presets/monoid/combined-structure-add-maximum.hpp"

namespace luz::monoid {

  template < typename T >
  class RangeAddRangeMaximumQueryMonoid {
    using V  = RangeMaximumQueryMonoid< T >;
    using VT = typename V::value_type;
    using O  = RangeAddQueryMonoid< T >;
    using OT = typename O::value_type;

   public:
    using value_structure    = V;
    using operator_structure = O;

    static constexpr T operation(VT a, OT b) {
      return a + b;
    }
  };

} // namespace luz::monoid