alg/acted_monoid/maxidx_add.hpp

View this file on GitHub
Last update: 2023-02-01 23:31:55+09:00
Include: #include "alg/acted_monoid/maxidx_add.hpp"

Depends on

Verified with

test/mytest/maxidx_add.test.cpp

Code

#include "alg/monoid/add.hpp"
#include "alg/monoid/max_idx.hpp"

template <typename E, bool tie_is_left = true>
struct ActedMonoid_MaxIdx_Add {
  using Monoid_X = Monoid_Max_Idx<E, tie_is_left>;
  using Monoid_A = Monoid_Add<E>;
  using X = typename Monoid_X::value_type;
  using A = typename Monoid_A::value_type;
  static constexpr X act(const X &x, const A &a, const ll &size) {
    if (x.fi == -infty<E>) return x;
    return {x.fi + a, x.se};
  }
};

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

template <typename X>
struct Monoid_Add {
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 2 "alg/monoid/max_idx.hpp"

template <typename T, bool tie_is_left = true>
struct Monoid_Max_Idx {
  using value_type = pair<T, int>;
  using X = value_type;
  static X op(X x, X y) {
    if (x.fi > y.fi) return x;
    if (x.fi < y.fi) return y;
    if (x.se > y.se) swap(x, y);
    return (tie_is_left ? x : y);
  }
  static constexpr X unit() { return {-infty<T>, -1}; }
  static constexpr bool commute = true;
};
#line 3 "alg/acted_monoid/maxidx_add.hpp"

template <typename E, bool tie_is_left = true>
struct ActedMonoid_MaxIdx_Add {
  using Monoid_X = Monoid_Max_Idx<E, tie_is_left>;
  using Monoid_A = Monoid_Add<E>;
  using X = typename Monoid_X::value_type;
  using A = typename Monoid_A::value_type;
  static constexpr X act(const X &x, const A &a, const ll &size) {
    if (x.fi == -infty<E>) return x;
    return {x.fi + a, x.se};
  }
};