Monotone Minima
(dp/monotone_minima.hpp)

• View this file on GitHub
• Last update: 2024-01-08 01:32:22+09:00
• Include: #include "dp/monotone_minima.hpp"

Description

Monotone minima は，monotone 行列の各行の argmin を高速に求めるアルゴリズムである．

$n \times m$ 行列 $A$ が monotone であるとは，

$\mathrm{argmin} A_{i,\ast} \leq \mathrm{argmin} A_{i+1,\ast}$ が成り立つことである．

$A$ が更に totally monotone ($A$ の任意の部分行列が monotone) であれば，SMAWK algorithm という更に高速なアルゴリズムが存在する．

• vector<int> monotone_minima(int n, int m, F f)
  • $A_{i,j}=f(i,j)$ である $n \times m$ 行列 $A$ の各行の argmin を求める
  • 時間計算量: $O((n + m)\log n)$

Reference

• Totally Monotone Matrix Searching (SMAWK algorithm)

Required by

• Convex Min-Plus Convolution (convolution/convex_min_plus_convolution.hpp)

Verified with

• test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp

Code

#pragma once
#include <vector>

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F& f) {
    std::vector<int> idx(n, -1);

    auto calc = [&](const auto& calc, int l, int r, int optl,
                    int optr) -> void {
        if (l > r) return;
        int m = std::midpoint(l, r);
        auto mi = f(m, optl);
        idx[m] = optl;
        for (int i = optl + 1; i <= optr; ++i) {
            auto v = f(m, i);
            if (mi > v) {
                mi = v;
                idx[m] = i;
            }
        }
        calc(calc, l, m - 1, optl, idx[m]);
        calc(calc, m + 1, r, idx[m], optr);
    };

    calc(calc, 0, n - 1, 0, m - 1);
    return idx;
}

#line 2 "dp/monotone_minima.hpp"
#include <vector>

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F& f) {
    std::vector<int> idx(n, -1);

    auto calc = [&](const auto& calc, int l, int r, int optl,
                    int optr) -> void {
        if (l > r) return;
        int m = std::midpoint(l, r);
        auto mi = f(m, optl);
        idx[m] = optl;
        for (int i = optl + 1; i <= optr; ++i) {
            auto v = f(m, i);
            if (mi > v) {
                mi = v;
                idx[m] = i;
            }
        }
        calc(calc, l, m - 1, optl, idx[m]);
        calc(calc, m + 1, r, idx[m], optr);
    };

    calc(calc, 0, n - 1, 0, m - 1);
    return idx;
}

Back to top page