library/monotone/MonotoneMinima.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/monotone/MonotoneMinima.hpp"

Depends on

build/pch/stdc++.hpp

Code

template <typename F>
std::vector<int> internal_monotone_minima(int u, int d, int l, int r,
                                          const F &argmin) {
    if (u == d)
        return {};
    std::vector<int> ret(d - u);
    int m = (u + d) >> 1;
    ret[m - u] = argmin(m, l, r);
    auto v1 = internal_monotone_minima(u, m, l, ret[m - u] + 1, argmin);
    std::ranges::copy(v1, ret.begin());
    auto v2 = internal_monotone_minima(m + 1, d, ret[m - u], r, argmin);
    std::ranges::copy(v2, ret.begin() + m - u + 1);
    return ret;
}

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F &argmin) {
    return internal_monotone_minima(0, n, 0, m, argmin);
}

#line 1 "library/monotone/MonotoneMinima.hpp"
template <typename F>
std::vector<int> internal_monotone_minima(int u, int d, int l, int r,
                                          const F &argmin) {
    if (u == d)
        return {};
    std::vector<int> ret(d - u);
    int m = (u + d) >> 1;
    ret[m - u] = argmin(m, l, r);
    auto v1 = internal_monotone_minima(u, m, l, ret[m - u] + 1, argmin);
    std::ranges::copy(v1, ret.begin());
    auto v2 = internal_monotone_minima(m + 1, d, ret[m - u], r, argmin);
    std::ranges::copy(v2, ret.begin() + m - u + 1);
    return ret;
}

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F &argmin) {
    return internal_monotone_minima(0, n, 0, m, argmin);
}