Monotone Minima
(algorithm/monotone_minima.hpp)

• View this file on GitHub
• Last update: 2023-11-08 11:18:30+09:00
• Include: #include "algorithm/monotone_minima.hpp"

説明

Monotoneな行列の各行の行最小値を求める。 $O(N + M\log N)$

monotone_minima(n, m, f, compare)

$n \times m$ の行列に対してmonotone minimaを行う。 $f(i, j)$ は行列の $(i, j)$ 成分を返す。また、compareは比較関数を与える。デフォルトはminである。

slide_monotone_minima(n, m, f, compare)

$n \times m$ の行列に対してmonotone minimaを行う。 $f(i, j, depth)$ は行列の $(i, j)$ 成分を返す。ここで、再帰の深さ毎にカーソルを持つことでスライドでの行列成分のアクセスを可能にする。また、compareは比較関数を与える。デフォルトはminである。

Required by

• Enumerate Monge d-edge shortest path (algorithm/enumerate_monge_d_edge_shortest_path.hpp)
• Min Plus Convolution (convolution/min_plus_convolution.hpp)

Verified with

• test/convolution/Min_Plus_Convolution_Convex_and_Arbitary.test.cpp
• test/yuki/yuki_952.test.cpp

Code

#pragma once

#include <functional>
#include <utility>
#include <vector>

namespace ebi {

template <class F,
          class T = decltype(std::declval<F>()(std::declval<int>(),
                                               std::declval<int>())),
          class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left,
                   int right) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid]);
        self(self, mid + 1, bottom, argmin[mid], right);
    };
    dfs(dfs, 0, n - 1, 0, m - 1);
    return {argmin, min_val};
}

template <class T, class F, class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> slide_monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left, int right,
                   int depth) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left, depth);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i, depth);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid], depth + 1);
        self(self, mid + 1, bottom, argmin[mid], right, depth + 1);
    };
    dfs(dfs, 0, n - 1, 0, m - 1, 0);
    return {argmin, min_val};
}

}  // namespace ebi

#line 2 "algorithm/monotone_minima.hpp"

#include <functional>
#include <utility>
#include <vector>

namespace ebi {

template <class F,
          class T = decltype(std::declval<F>()(std::declval<int>(),
                                               std::declval<int>())),
          class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left,
                   int right) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid]);
        self(self, mid + 1, bottom, argmin[mid], right);
    };
    dfs(dfs, 0, n - 1, 0, m - 1);
    return {argmin, min_val};
}

template <class T, class F, class Compare = std::less<T>>
std::pair<std::vector<int>, std::vector<T>> slide_monotone_minima(
    int n, int m, F f, const Compare &compare = Compare()) {
    std::vector<int> argmin(n);
    std::vector<T> min_val(n);
    auto dfs = [&](auto &&self, int top, int bottom, int left, int right,
                   int depth) -> void {
        if (top > bottom) return;
        int mid = (top + bottom) >> 1;
        argmin[mid] = left;
        min_val[mid] = f(mid, left, depth);
        for (int i = left + 1; i <= right; i++) {
            T val = f(mid, i, depth);
            if (min_val[mid] == val || compare(val, min_val[mid])) {
                argmin[mid] = i;
                min_val[mid] = val;
            }
        }
        self(self, top, mid - 1, left, argmin[mid], depth + 1);
        self(self, mid + 1, bottom, argmin[mid], right, depth + 1);
    };
    dfs(dfs, 0, n - 1, 0, m - 1, 0);
    return {argmin, min_val};
}

}  // namespace ebi

Back to top page