alg/monoid/min_idx.hpp

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

Required by

• alg/acted_monoid/minidx_add.hpp
• geo/manhattan_nns.hpp

Verified with

• test/mytest/manhattan_nns.test.cpp
• test/mytest/minidx_add.test.cpp
• test/mytest/suffix_tree.test.cpp
• test/yukicoder/2361.test.cpp
• test_atcoder/abc301h.test.cpp

Code

#pragma once

template <typename T, bool tie_is_left = true>
struct Monoid_Min_Idx {
  using value_type = pair<T, int>;
  using X = value_type;
  static constexpr bool is_small(const X& x, const X& y) {
    if (x.fi < y.fi) return true;
    if (x.fi > y.fi) return false;
    return (tie_is_left ? (x.se < y.se) : (x.se >= y.se));
  }
  static X op(X x, X y) { return (is_small(x, y) ? x : y); }
  static constexpr X unit() { return {infty<T>, -1}; }
  static constexpr bool commute = true;
};

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

template <typename T, bool tie_is_left = true>
struct Monoid_Min_Idx {
  using value_type = pair<T, int>;
  using X = value_type;
  static constexpr bool is_small(const X& x, const X& y) {
    if (x.fi < y.fi) return true;
    if (x.fi > y.fi) return false;
    return (tie_is_left ? (x.se < y.se) : (x.se >= y.se));
  }
  static X op(X x, X y) { return (is_small(x, y) ? x : y); }
  static constexpr X unit() { return {infty<T>, -1}; }
  static constexpr bool commute = true;
};

Back to top page