alg/monoid/maxidx.hpp

• View this file on GitHub
• Last update: 2026-08-17 08:30:43+09:00
• Include: #include "alg/monoid/maxidx.hpp"

Required by

• alg/acted_monoid/maxidx_add.hpp

Verified with

• test/1_mytest/maxidx_add.test.cpp
• test/3_yukicoder/529.test.cpp

Code

template <typename T, bool tie_is_left = true>
struct Monoid_MaxIdx {
  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 1 "alg/monoid/maxidx.hpp"

template <typename T, bool tie_is_left = true>
struct Monoid_MaxIdx {
  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;
};

Back to top page