opt/monotone_minima.hpp

• View this file on GitHub
• Last update: 2025-08-27 11:36:50+09:00
• Include: #include "opt/monotone_minima.hpp"

Required by

• convolution/min_plus_convolution.hpp

Verified with

• convolution/test/min_plus_convolution_convex_arbitrary.test.cpp
• convolution/test/min_plus_convolution_convex_convex.test.cpp

Code

#pragma once
#include <vector>

// f(i, j, k) = true <=> (i, j) -> (i, k)
// j < k.
template <typename F>
std::vector<int> monotone_minima(int h, int w, F f) {
    std::vector<int> argmin(h);
    auto rec = [&](auto rec, int xl, int xr, int yl, int yr) -> void {
        if (xl == xr) {
            return;
        }
        int xm = (xl + xr) / 2;
        argmin[xm] = yl;
        for (int i = yl + 1; i < yr; ++i) {
            if (f(xm, argmin[xm], i)) {
                argmin[xm] = i;
            }
        }
        rec(rec, xl, xm, yl, argmin[xm] + 1);
        rec(rec, xm + 1, xr, argmin[xm], yr);
    };
    rec(rec, 0, h, 0, w);
    return argmin;
}

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

// f(i, j, k) = true <=> (i, j) -> (i, k)
// j < k.
template <typename F>
std::vector<int> monotone_minima(int h, int w, F f) {
    std::vector<int> argmin(h);
    auto rec = [&](auto rec, int xl, int xr, int yl, int yr) -> void {
        if (xl == xr) {
            return;
        }
        int xm = (xl + xr) / 2;
        argmin[xm] = yl;
        for (int i = yl + 1; i < yr; ++i) {
            if (f(xm, argmin[xm], i)) {
                argmin[xm] = i;
            }
        }
        rec(rec, xl, xm, yl, argmin[xm] + 1);
        rec(rec, xm + 1, xr, argmin[xm], yr);
    };
    rec(rec, 0, h, 0, w);
    return argmin;
}

Back to top page