library/convex/MonotoneMinima.hpp

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

Depends on

build/pch/stdc++.hpp

Code

#pragma once
#include <queue>
#include <tuple>
#include <vector>

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F &argmin) {
    // argmin(i,l,r) : argmin_{j\in[l,r)} A[i][j]
    std::vector<int> res(n);
    std::queue<std::tuple<int, int, int, int>> que;
    que.emplace(0, n, 0, m);

    while (que.size()) {
        auto [u, d, l, r] = que.front();
        que.pop();

        if (u == d)
            continue;
        int m = (u + d) >> 1;
        res[m] = argmin(m, l, r);
        que.emplace(u, m, l, res[m] + 1);
        que.emplace(m + 1, d, res[m], r);
    }
    return res;
}

#line 2 "library/convex/MonotoneMinima.hpp"
#include <queue>
#include <tuple>
#include <vector>

template <typename F>
std::vector<int> monotone_minima(int n, int m, const F &argmin) {
    // argmin(i,l,r) : argmin_{j\in[l,r)} A[i][j]
    std::vector<int> res(n);
    std::queue<std::tuple<int, int, int, int>> que;
    que.emplace(0, n, 0, m);

    while (que.size()) {
        auto [u, d, l, r] = que.front();
        que.pop();

        if (u == d)
            continue;
        int m = (u + d) >> 1;
        res[m] = argmin(m, l, r);
        que.emplace(u, m, l, res[m] + 1);
        que.emplace(m + 1, d, res[m], r);
    }
    return res;
}