alg/monoid/minmincnt.hpp

• View this file on GitHub
• Last update: 2023-04-02 02:09:38+09:00
• Include: #include "alg/monoid/minmincnt.hpp"

Required by

• alg/acted_monoid/minmincnt_add.hpp
• ds/rectangle_union.hpp
• graph/count/count_connected_intervals.hpp

Verified with

• test/aoj/DSL_4_A.test.cpp
• test/library_checker/datastructure/area_of_union_of_rectangles.test.cpp
• test_atcoder/abc318b.test.cpp

Code

#pragma once

// 最小値、最小値の個数

template <typename E>
struct Monoid_MinMincnt {
  using value_type = pair<E, E>;
  using X = value_type;
  static X op(X x, X y) {
    auto [xmin, xmincnt] = x;
    auto [ymin, ymincnt] = y;
    if (xmin > ymin) return y;
    if (xmin < ymin) return x;
    return {xmin, xmincnt + ymincnt};
  }
  static constexpr X unit() { return {infty<E>, 0}; }
  static constexpr bool commute = true;
};

#line 2 "alg/monoid/minmincnt.hpp"

// 最小値、最小値の個数

template <typename E>
struct Monoid_MinMincnt {
  using value_type = pair<E, E>;
  using X = value_type;
  static X op(X x, X y) {
    auto [xmin, xmincnt] = x;
    auto [ymin, ymincnt] = y;
    if (xmin > ymin) return y;
    if (xmin < ymin) return x;
    return {xmin, xmincnt + ymincnt};
  }
  static constexpr X unit() { return {infty<E>, 0}; }
  static constexpr bool commute = true;
};

Back to top page