Monotone minima
(Mylib/DynamicProgramming/SpeedupTechnique/monotone_minima.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00

Operations

Requirements

Notes

Problems

• C - スペースエクスプローラー高橋君

References

• https://ei1333.github.io/luzhiled/snippets/dp/monotone-minima.html
• https://ferin-tech.hatenablog.com/entry/2018/02/23/071343
• https://wiki.kimiyuki.net/monotone%20minima

Code

#pragma once
#include <utility>
#include <vector>

namespace haar_lib {
  namespace monotone_minima_impl {
    template <typename T, typename F>
    auto rec(
        int N, int M, const F &f, int top, int bottom, int left, int right,
        std::vector<std::pair<int, T>> &ret) {
      if (top > bottom) return;
      if (top == bottom) {
        const int i = top;

        int index = left;
        T m       = f(i, index);

        for (int j = left; j <= right; ++j) {
          const auto temp = f(i, j);
          if (temp < m) {
            m     = temp;
            index = j;
          }
        }

        ret[i] = std::make_pair(index, m);
        return;
      }

      const int mid = (top + bottom) / 2;
      rec(N, M, f, mid, mid, left, right, ret);
      rec(N, M, f, top, mid - 1, left, ret[mid].first, ret);
      rec(N, M, f, mid + 1, bottom, ret[mid].first, right, ret);
    }
  }  // namespace monotone_minima_impl

  template <typename T, typename F>
  auto monotone_minima(int N, int M, const F &f) {
    std::vector<std::pair<int, T>> ret(M);
    monotone_minima_impl::rec<T, F>(N, M, f, 0, N - 1, 0, M - 1, ret);

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/DynamicProgramming/SpeedupTechnique/monotone_minima.cpp"
#include <utility>
#include <vector>

namespace haar_lib {
  namespace monotone_minima_impl {
    template <typename T, typename F>
    auto rec(
        int N, int M, const F &f, int top, int bottom, int left, int right,
        std::vector<std::pair<int, T>> &ret) {
      if (top > bottom) return;
      if (top == bottom) {
        const int i = top;

        int index = left;
        T m       = f(i, index);

        for (int j = left; j <= right; ++j) {
          const auto temp = f(i, j);
          if (temp < m) {
            m     = temp;
            index = j;
          }
        }

        ret[i] = std::make_pair(index, m);
        return;
      }

      const int mid = (top + bottom) / 2;
      rec(N, M, f, mid, mid, left, right, ret);
      rec(N, M, f, top, mid - 1, left, ret[mid].first, ret);
      rec(N, M, f, mid + 1, bottom, ret[mid].first, right, ret);
    }
  }  // namespace monotone_minima_impl

  template <typename T, typename F>
  auto monotone_minima(int N, int M, const F &f) {
    std::vector<std::pair<int, T>> ret(M);
    monotone_minima_impl::rec<T, F>(N, M, f, 0, N - 1, 0, M - 1, ret);

    return ret;
  }
}  // namespace haar_lib

Back to top page