alg/monoid/add_chmax.hpp

• View this file on GitHub
• Last update: 2023-02-01 23:31:55+09:00
• Include: #include "alg/monoid/add_chmax.hpp"
• Link: View error logs on GitHub Actions

Verified with

• test/3_yukicoder/1524.test.cpp

Code

#pragma once

// max(x+a,b) と表せる関数の合成

template <typename E>
struct Monoid_Add_Chmax {
  using value_type = pair<E, E>;
  using X = value_type;
  static X op(X x, X y) {
    auto [a, c] = x;
    auto [d, f] = y;
    a = a + d;
    c = (c == -infty<E> ? c : c + d);
    c = max(c, f);
    return {a, c};
  }

  static E eval(X f, E x) { return max(x + f.fi, f.se); }
  static X add(E a) { return {a, -infty<E>}; }
  static X chmax(E c) { return {0, c}; }

  static constexpr X unit() { return {0, -infty<E>}; }
  static constexpr bool commute = 0;
};

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

// max(x+a,b) と表せる関数の合成

template <typename E>
struct Monoid_Add_Chmax {
  using value_type = pair<E, E>;
  using X = value_type;
  static X op(X x, X y) {
    auto [a, c] = x;
    auto [d, f] = y;
    a = a + d;
    c = (c == -infty<E> ? c : c + d);
    c = max(c, f);
    return {a, c};
  }

  static E eval(X f, E x) { return max(x + f.fi, f.se); }
  static X add(E a) { return {a, -infty<E>}; }
  static X chmax(E c) { return {0, c}; }

  static constexpr X unit() { return {0, -infty<E>}; }
  static constexpr bool commute = 0;
};

Back to top page