Monotone Minima
(src/optimization/monotone_minima.hpp)

• View this file on GitHub
• Last update: 2024-06-01 01:35:37+09:00
• Include: #include "src/optimization/monotone_minima.hpp"

概要

totally monotone な $N \times M$ 行列 $A$ を入力として，各 $i$ について $\underset{j}{\operatorname{argmin}}\ A_{i, j}$ を $\mathrm{O}(N + M \log N)$ 時間で求める． 実装中の関数 select(i, j, k) は $j < k$ が保証されているもとで，$A_{i, j}$ よりも $A_{i, k}$ が好ましいとされる場合に true を，そうでないときは false を返す関数である．

計算量は SMAWK algorithm に劣るが，定数倍の関係上実用的には SMAWK algorithm より高速なケースが多い．

Required by

• Min Plus Convolution (Convex and Arbitary) (src/convolution/min_plus_convolution_convex_arbitrary.hpp)

Verified with

• test/yosupo/min_plus_convolution_convex_arbitrary.test.cpp

Code

#pragma once
#include <vector>

template <class Select> std::vector<int> monotone_minima(int n, int m, const Select& select) {
    std::vector<int> res(n);
    auto dfs = [&](auto self, int u, int d, int l, int r) -> void {
        if (u == d) return;
        int m = (u + d) >> 1;
        int argmin = l;
        for (int col = l + 1; col < r; col++) {
            if (select(m, argmin, col)) {
                argmin = col;
            }
        }
        res[m] = argmin;
        self(self, u, m, l, argmin + 1);
        self(self, m + 1, d, argmin, r);
    };
    dfs(dfs, 0, n, 0, m);
    return res;
}

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

template <class Select> std::vector<int> monotone_minima(int n, int m, const Select& select) {
    std::vector<int> res(n);
    auto dfs = [&](auto self, int u, int d, int l, int r) -> void {
        if (u == d) return;
        int m = (u + d) >> 1;
        int argmin = l;
        for (int col = l + 1; col < r; col++) {
            if (select(m, argmin, col)) {
                argmin = col;
            }
        }
        res[m] = argmin;
        self(self, u, m, l, argmin + 1);
        self(self, m + 1, d, argmin, r);
    };
    dfs(dfs, 0, n, 0, m);
    return res;
}

Back to top page