Structured Min-Plus and Max-Plus Convolution
(convex/monge/min_plus_convolution.hpp)

View this file on GitHub
Last update: 2026-07-07 18:38:36+09:00
Include: #include "convex/monge/min_plus_convolution.hpp"

Overview

For arrays a and b, min-plus convolution is

\[c[k] = \min_{i+j=k}(a[i] + b[j]).\]

When b is a discrete convex sequence, the minimizing index in a is nondecreasing with k. min_plus_convolution_convex applies SMAWK to this implicit Monge matrix and computes every minimum in linear time. Only the second sequence must be convex; the first may be arbitrary.

The header also provides the symmetric max_plus_convolution_concave. Only its second sequence must be concave, meaning that its adjacent differences are nonincreasing.

When both inputs are structured, min_plus_convolution_convex_convex and max_plus_convolution_concave_concave merge their adjacent differences directly. These specializations have the same linear asymptotic complexity but smaller constants than the SMAWK-based one-sided functions.

Functions

template <class T>
std::vector<T> min_plus_convolution_convex(
    const std::vector<T>& arbitrary,
    const std::vector<T>& convex
);

template <class T>
std::vector<T> min_plus_convolution_convex(
    const std::vector<T>& arbitrary,
    const std::vector<T>& convex,
    const T& infinity
);

template <class T>
std::vector<T> min_plus_convolution_convex_convex(
    const std::vector<T>& first,
    const std::vector<T>& second
);

template <class T>
std::vector<T> min_plus_convolution_convex_convex(
    const std::vector<T>& first,
    const std::vector<T>& second,
    const T& infinity
);

template <class T>
std::vector<T> max_plus_convolution_concave(
    const std::vector<T>& arbitrary,
    const std::vector<T>& concave
);

template <class T>
std::vector<T> max_plus_convolution_concave(
    const std::vector<T>& arbitrary,
    const std::vector<T>& concave,
    const T& negative_infinity
);

template <class T>
std::vector<T> max_plus_convolution_concave_concave(
    const std::vector<T>& first,
    const std::vector<T>& second
);

template <class T>
std::vector<T> max_plus_convolution_concave_concave(
    const std::vector<T>& first,
    const std::vector<T>& second,
    const T& negative_infinity
);

For min_plus_convolution_convex, the first sequence is arbitrary and the second must have nondecreasing adjacent differences. For max_plus_convolution_concave, the first sequence is arbitrary and the second must have nonincreasing adjacent differences. Both inputs to the specialized functions must have the corresponding structure.

The three-argument overloads treat the last argument as an absorbing extended value. For min-plus, infinity + x is infinity; for max-plus, negative_infinity + x is negative_infinity. The finite entries of each structured input must form one contiguous convex or concave interval. Infinity may occur before or after that interval, so {0, 1, infinity, infinity} is a valid extended convex sequence. The arbitrary input may contain the sentinel at any indices; those candidates are omitted from SMAWK, and result indices with no finite decomposition remain infinite. Values are recognized as infinite by equality with the supplied sentinel, so no finite input or finite sum may equal that value. The sentinel does not need to be the numeric maximum or minimum of T.

The two-argument overloads continue to treat every value as an ordinary element of T.

If either sequence is empty, the result is empty. Otherwise its length is the sum of the input lengths minus one.

The precondition helpers are:

template <class T>
bool is_convex_sequence(const std::vector<T>& sequence);

template <class T>
bool is_convex_sequence(
    const std::vector<T>& sequence,
    const T& infinity
);

template <class T>
bool is_concave_sequence(const std::vector<T>& sequence);

template <class T>
bool is_concave_sequence(
    const std::vector<T>& sequence,
    const T& negative_infinity
);

The sentinel-aware helpers check that the finite domain is contiguous in addition to checking its adjacent differences. An all-infinity sequence is accepted. The convolution functions do not run these checks automatically.

Complexity

For input lengths N and M:

Function	Time	Memory, including the result
`min_plus_convolution_convex`	$O(N + M)$	$O(N + M)$
`min_plus_convolution_convex(..., infinity)`	$O(N + M)$	$O(N + M)$
`min_plus_convolution_convex_convex`	$O(N + M)$	$O(N + M)$
`min_plus_convolution_convex_convex(..., infinity)`	$O(N + M)$	$O(N + M)$
`max_plus_convolution_concave`	$O(N + M)$	$O(N + M)$
`max_plus_convolution_concave(..., negative_infinity)`	$O(N + M)$	$O(N + M)$
`max_plus_convolution_concave_concave`	$O(N + M)$	$O(N + M)$
`max_plus_convolution_concave_concave(..., negative_infinity)`	$O(N + M)$	$O(N + M)$
`is_convex_sequence`	$O(N)$	$O(1)$
`is_concave_sequence`	$O(N)$	$O(1)$

The convolution element type must support addition and comparison. The sentinel-aware overloads additionally require equality comparison. The precondition helpers and two-structured specializations require subtraction. Finite intermediate sums and adjacent differences must fit in the type.

Example

#include "convex/monge/min_plus_convolution.hpp"
#include <vector>

int main() {
    std::vector<long long> first = {4, -3, 8, 1};
    std::vector<long long> second = {1, 2, 5, 10};

    auto result = m1une::convex::min_plus_convolution_convex(first, second);

    std::vector<long long> another_convex = {0, 3, 8, 15};
    auto structured = m1une::convex::min_plus_convolution_convex_convex(
        another_convex, second);

    constexpr long long infinity = 2'000'000'000'000'000'000LL;
    std::vector<long long> extended_convex = {0, 1, infinity, infinity};
    auto extended = m1une::convex::min_plus_convolution_convex(
        first, extended_convex, infinity);

    std::vector<long long> first_max = {2, 9, -1, 5};
    std::vector<long long> second_concave = {-1, -2, -5, -10};
    auto maximum =
        m1une::convex::max_plus_convolution_concave(first_max, second_concave);
}

Depends on

SMAWK (convex/monge/smawk.hpp)

Required by

Verified with

Code

#ifndef M1UNE_CONVEX_MONGE_MIN_PLUS_CONVOLUTION_HPP
#define M1UNE_CONVEX_MONGE_MIN_PLUS_CONVOLUTION_HPP 1

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

#include "smawk.hpp"

namespace m1une {
namespace convex {

namespace convolution_detail {

template <class T, class Compare, class Add>
std::vector<T> structured_convolution(const std::vector<T>& arbitrary,
                                      const std::vector<T>& structured,
                                      Compare compare, Add add) {
    if (arbitrary.empty() || structured.empty()) return {};

    int first_size = int(arbitrary.size());
    int second_size = int(structured.size());
    int result_size = first_size + second_size - 1;
    auto select = [&](int index, int current, int candidate) {
        if (index < candidate) return false;
        if (index - current >= second_size) return true;
        T current_value = add(arbitrary[current], structured[index - current]);
        T candidate_value = add(arbitrary[candidate], structured[index - candidate]);
        return !compare(current_value, candidate_value);
    };

    std::vector<int> optima =
        smawk_detail::row_optima(result_size, first_size, select);
    std::vector<T> result;
    result.reserve(result_size);
    for (int index = 0; index < result_size; index++) {
        int first_index = optima[index];
        result.emplace_back(add(arbitrary[first_index],
                                structured[index - first_index]));
    }
    return result;
}

template <class T>
std::pair<int, int> finite_interval(const std::vector<T>& sequence,
                                    const T& infinity) {
    int left = 0;
    while (left < int(sequence.size()) && sequence[left] == infinity) left++;
    int right = int(sequence.size());
    while (right > left && sequence[right - 1] == infinity) right--;
    return {left, right};
}

template <class T, class Compare>
std::vector<T> structured_convolution_with_infinity(
    const std::vector<T>& arbitrary, const std::vector<T>& structured,
    const T& infinity, Compare compare) {
    if (arbitrary.empty() || structured.empty()) return {};

    auto [left, right] = finite_interval(structured, infinity);
    int result_size = int(arbitrary.size() + structured.size() - 1);
    std::vector<T> result(result_size, infinity);
    if (left == right) return result;

    std::vector<int> columns;
    columns.reserve(arbitrary.size());
    for (int i = 0; i < int(arbitrary.size()); i++) {
        if (arbitrary[i] != infinity) columns.push_back(i);
    }
    if (columns.empty()) return result;

    int finite_size = right - left;
    int middle_size = int(arbitrary.size()) + finite_size - 1;
    std::vector<int> rows;
    rows.reserve(middle_size);
    int active = 0;
    for (int row = 0; row < middle_size; row++) {
        if (row < int(arbitrary.size()) && arbitrary[row] != infinity) active++;
        if (row >= finite_size && arbitrary[row - finite_size] != infinity) active--;
        if (active > 0) rows.push_back(row);
    }

    auto select = [&](int index, int current, int candidate) {
        if (index < candidate) return false;
        if (index - current >= finite_size) return true;
        T current_value =
            arbitrary[current] + structured[left + index - current];
        T candidate_value =
            arbitrary[candidate] + structured[left + index - candidate];
        return !compare(current_value, candidate_value);
    };
    std::vector<int> optima(middle_size, -1);
    smawk_detail::solve(rows, columns, select, optima);
    for (int row : rows) {
        int first_index = optima[row];
        result[left + row] =
            arbitrary[first_index] + structured[left + row - first_index];
    }
    return result;
}

template <class T, class Compare>
std::vector<T> linear_structured_convolution(const std::vector<T>& first,
                                             const std::vector<T>& second,
                                             Compare compare) {
    if (first.empty() || second.empty()) return {};

    int first_size = int(first.size());
    int second_size = int(second.size());
    std::vector<T> result(first_size + second_size - 1);
    result[0] = first[0] + second[0];

    int first_index = 1;
    int second_index = 1;
    int result_index = 1;
    while (first_index < first_size && second_index < second_size) {
        T first_difference = first[first_index] - first[first_index - 1];
        T second_difference = second[second_index] - second[second_index - 1];
        if (compare(second_difference, first_difference)) {
            result[result_index] = result[result_index - 1] + second_difference;
            second_index++;
        } else {
            result[result_index] = result[result_index - 1] + first_difference;
            first_index++;
        }
        result_index++;
    }
    while (first_index < first_size) {
        T difference = first[first_index] - first[first_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        first_index++;
        result_index++;
    }
    while (second_index < second_size) {
        T difference = second[second_index] - second[second_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        second_index++;
        result_index++;
    }
    return result;
}

template <class T, class Compare>
std::vector<T> linear_structured_convolution_with_infinity(
    const std::vector<T>& first, const std::vector<T>& second,
    const T& infinity, Compare compare) {
    if (first.empty() || second.empty()) return {};

    auto [first_left, first_right] = finite_interval(first, infinity);
    auto [second_left, second_right] = finite_interval(second, infinity);
    int result_size = int(first.size() + second.size() - 1);
    std::vector<T> result(result_size, infinity);
    if (first_left == first_right || second_left == second_right) return result;

    int offset = first_left + second_left;
    result[offset] = first[first_left] + second[second_left];

    int first_index = first_left + 1;
    int second_index = second_left + 1;
    int result_index = offset + 1;
    while (first_index < first_right && second_index < second_right) {
        T first_difference = first[first_index] - first[first_index - 1];
        T second_difference = second[second_index] - second[second_index - 1];
        if (compare(second_difference, first_difference)) {
            result[result_index] = result[result_index - 1] + second_difference;
            second_index++;
        } else {
            result[result_index] = result[result_index - 1] + first_difference;
            first_index++;
        }
        result_index++;
    }
    while (first_index < first_right) {
        T difference = first[first_index] - first[first_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        first_index++;
        result_index++;
    }
    while (second_index < second_right) {
        T difference = second[second_index] - second[second_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        second_index++;
        result_index++;
    }
    return result;
}

template <class T, class Compare>
bool is_structured_sequence_with_infinity(const std::vector<T>& sequence,
                                          const T& infinity, Compare violation) {
    auto [left, right] = finite_interval(sequence, infinity);
    for (int i = left; i < right; i++) {
        if (sequence[i] == infinity) return false;
    }
    for (int i = left + 1; i + 1 < right; i++) {
        T first_difference = sequence[i] - sequence[i - 1];
        T second_difference = sequence[i + 1] - sequence[i];
        if (violation(first_difference, second_difference)) return false;
    }
    return true;
}

}  // namespace convolution_detail

template <class T>
bool is_convex_sequence(const std::vector<T>& sequence) {
    for (int i = 1; i + 1 < int(sequence.size()); i++) {
        if (sequence[i] - sequence[i - 1] > sequence[i + 1] - sequence[i]) {
            return false;
        }
    }
    return true;
}

template <class T>
bool is_convex_sequence(const std::vector<T>& sequence, const T& infinity) {
    return convolution_detail::is_structured_sequence_with_infinity(
        sequence, infinity, std::greater<>());
}

template <class T>
bool is_concave_sequence(const std::vector<T>& sequence) {
    for (int i = 1; i + 1 < int(sequence.size()); i++) {
        if (sequence[i] - sequence[i - 1] < sequence[i + 1] - sequence[i]) {
            return false;
        }
    }
    return true;
}

template <class T>
bool is_concave_sequence(const std::vector<T>& sequence,
                         const T& negative_infinity) {
    return convolution_detail::is_structured_sequence_with_infinity(
        sequence, negative_infinity, std::less<>());
}

template <class T>
std::vector<T> min_plus_convolution_convex(const std::vector<T>& arbitrary,
                                           const std::vector<T>& convex) {
    auto add = [](const T& first, const T& second) { return first + second; };
    return convolution_detail::structured_convolution(arbitrary, convex,
                                                      std::less<>(), add);
}

template <class T>
std::vector<T> min_plus_convolution_convex(const std::vector<T>& arbitrary,
                                           const std::vector<T>& convex,
                                           const T& infinity) {
    return convolution_detail::structured_convolution_with_infinity(
        arbitrary, convex, infinity, std::less<>());
}

template <class T>
std::vector<T> min_plus_convolution_convex_convex(const std::vector<T>& first,
                                                  const std::vector<T>& second) {
    return convolution_detail::linear_structured_convolution(first, second, std::less<>());
}

template <class T>
std::vector<T> min_plus_convolution_convex_convex(
    const std::vector<T>& first, const std::vector<T>& second,
    const T& infinity) {
    return convolution_detail::linear_structured_convolution_with_infinity(
        first, second, infinity, std::less<>());
}

template <class T>
std::vector<T> max_plus_convolution_concave(const std::vector<T>& arbitrary,
                                            const std::vector<T>& concave) {
    auto add = [](const T& first, const T& second) { return first + second; };
    return convolution_detail::structured_convolution(arbitrary, concave,
                                                      std::greater<>(), add);
}

template <class T>
std::vector<T> max_plus_convolution_concave(const std::vector<T>& arbitrary,
                                            const std::vector<T>& concave,
                                            const T& negative_infinity) {
    return convolution_detail::structured_convolution_with_infinity(
        arbitrary, concave, negative_infinity, std::greater<>());
}

template <class T>
std::vector<T> max_plus_convolution_concave_concave(const std::vector<T>& first,
                                                    const std::vector<T>& second) {
    return convolution_detail::linear_structured_convolution(first, second, std::greater<>());
}

template <class T>
std::vector<T> max_plus_convolution_concave_concave(
    const std::vector<T>& first, const std::vector<T>& second,
    const T& negative_infinity) {
    return convolution_detail::linear_structured_convolution_with_infinity(
        first, second, negative_infinity, std::greater<>());
}

}  // namespace convex
}  // namespace m1une

#endif  // M1UNE_CONVEX_MONGE_MIN_PLUS_CONVOLUTION_HPP

#line 1 "convex/monge/min_plus_convolution.hpp"



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

#line 1 "convex/monge/smawk.hpp"



#include <cassert>
#line 6 "convex/monge/smawk.hpp"
#include <numeric>
#line 8 "convex/monge/smawk.hpp"

namespace m1une {
namespace convex {

namespace smawk_detail {

template <class Select>
void solve(const std::vector<int>& rows, const std::vector<int>& columns,
           const Select& select, std::vector<int>& answer) {
    if (rows.empty()) return;

    std::vector<int> reduced;
    reduced.reserve(columns.size());
    for (int column : columns) {
        while (!reduced.empty()) {
            int row = rows[int(reduced.size()) - 1];
            if (!select(row, reduced.back(), column)) break;
            reduced.pop_back();
        }
        if (reduced.size() < rows.size()) reduced.push_back(column);
    }

    std::vector<int> odd_rows;
    odd_rows.reserve(rows.size() / 2);
    for (int i = 1; i < int(rows.size()); i += 2) odd_rows.push_back(rows[i]);
    solve(odd_rows, reduced, select, answer);

    int left = 0;
    int right = 0;
    for (int i = 0; i < int(rows.size()); i += 2) {
        if (i + 1 < int(rows.size())) {
            while (reduced[right] != answer[rows[i + 1]]) right++;
        } else {
            right = int(reduced.size()) - 1;
        }

        int best = left;
        for (int j = left + 1; j <= right; j++) {
            if (select(rows[i], reduced[best], reduced[j])) {
                best = j;
            }
        }
        answer[rows[i]] = reduced[best];
        left = right;
    }
}

template <class Select>
std::vector<int> row_optima(int row_count, int column_count, const Select& select) {
    std::vector<int> answer(row_count, -1);
    if (row_count == 0 || column_count == 0) return answer;

    std::vector<int> rows(row_count), columns(column_count);
    std::iota(rows.begin(), rows.end(), 0);
    std::iota(columns.begin(), columns.end(), 0);
    solve(rows, columns, select, answer);
    return answer;
}

}  // namespace smawk_detail

template <class Value, class Compare = std::less<>>
std::vector<int> smawk_row_optima(int row_count, int column_count, Value value,
                                  Compare compare = Compare()) {
    assert(row_count >= 0);
    assert(column_count >= 0);
    return smawk_detail::row_optima(
        row_count, column_count,
        [&](int row, int current, int candidate) {
            return compare(value(row, candidate), value(row, current));
        });
}

template <class Value>
std::vector<int> smawk_row_argmin(int row_count, int column_count, Value value) {
    return smawk_row_optima(row_count, column_count, value, std::less<>());
}

template <class Value>
std::vector<int> smawk_row_argmax(int row_count, int column_count, Value value) {
    return smawk_row_optima(row_count, column_count, value, std::greater<>());
}

template <class T>
std::vector<int> smawk_row_argmin(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return smawk_row_argmin(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

template <class T>
std::vector<int> smawk_row_argmax(const std::vector<std::vector<T>>& matrix) {
    int row_count = int(matrix.size());
    int column_count = row_count == 0 ? 0 : int(matrix[0].size());
    for (const auto& row : matrix) assert(int(row.size()) == column_count);
    return smawk_row_argmax(
        row_count, column_count,
        [&](int row, int column) -> const T& { return matrix[row][column]; });
}

}  // namespace convex
}  // namespace m1une


#line 9 "convex/monge/min_plus_convolution.hpp"

namespace m1une {
namespace convex {

namespace convolution_detail {

template <class T, class Compare, class Add>
std::vector<T> structured_convolution(const std::vector<T>& arbitrary,
                                      const std::vector<T>& structured,
                                      Compare compare, Add add) {
    if (arbitrary.empty() || structured.empty()) return {};

    int first_size = int(arbitrary.size());
    int second_size = int(structured.size());
    int result_size = first_size + second_size - 1;
    auto select = [&](int index, int current, int candidate) {
        if (index < candidate) return false;
        if (index - current >= second_size) return true;
        T current_value = add(arbitrary[current], structured[index - current]);
        T candidate_value = add(arbitrary[candidate], structured[index - candidate]);
        return !compare(current_value, candidate_value);
    };

    std::vector<int> optima =
        smawk_detail::row_optima(result_size, first_size, select);
    std::vector<T> result;
    result.reserve(result_size);
    for (int index = 0; index < result_size; index++) {
        int first_index = optima[index];
        result.emplace_back(add(arbitrary[first_index],
                                structured[index - first_index]));
    }
    return result;
}

template <class T>
std::pair<int, int> finite_interval(const std::vector<T>& sequence,
                                    const T& infinity) {
    int left = 0;
    while (left < int(sequence.size()) && sequence[left] == infinity) left++;
    int right = int(sequence.size());
    while (right > left && sequence[right - 1] == infinity) right--;
    return {left, right};
}

template <class T, class Compare>
std::vector<T> structured_convolution_with_infinity(
    const std::vector<T>& arbitrary, const std::vector<T>& structured,
    const T& infinity, Compare compare) {
    if (arbitrary.empty() || structured.empty()) return {};

    auto [left, right] = finite_interval(structured, infinity);
    int result_size = int(arbitrary.size() + structured.size() - 1);
    std::vector<T> result(result_size, infinity);
    if (left == right) return result;

    std::vector<int> columns;
    columns.reserve(arbitrary.size());
    for (int i = 0; i < int(arbitrary.size()); i++) {
        if (arbitrary[i] != infinity) columns.push_back(i);
    }
    if (columns.empty()) return result;

    int finite_size = right - left;
    int middle_size = int(arbitrary.size()) + finite_size - 1;
    std::vector<int> rows;
    rows.reserve(middle_size);
    int active = 0;
    for (int row = 0; row < middle_size; row++) {
        if (row < int(arbitrary.size()) && arbitrary[row] != infinity) active++;
        if (row >= finite_size && arbitrary[row - finite_size] != infinity) active--;
        if (active > 0) rows.push_back(row);
    }

    auto select = [&](int index, int current, int candidate) {
        if (index < candidate) return false;
        if (index - current >= finite_size) return true;
        T current_value =
            arbitrary[current] + structured[left + index - current];
        T candidate_value =
            arbitrary[candidate] + structured[left + index - candidate];
        return !compare(current_value, candidate_value);
    };
    std::vector<int> optima(middle_size, -1);
    smawk_detail::solve(rows, columns, select, optima);
    for (int row : rows) {
        int first_index = optima[row];
        result[left + row] =
            arbitrary[first_index] + structured[left + row - first_index];
    }
    return result;
}

template <class T, class Compare>
std::vector<T> linear_structured_convolution(const std::vector<T>& first,
                                             const std::vector<T>& second,
                                             Compare compare) {
    if (first.empty() || second.empty()) return {};

    int first_size = int(first.size());
    int second_size = int(second.size());
    std::vector<T> result(first_size + second_size - 1);
    result[0] = first[0] + second[0];

    int first_index = 1;
    int second_index = 1;
    int result_index = 1;
    while (first_index < first_size && second_index < second_size) {
        T first_difference = first[first_index] - first[first_index - 1];
        T second_difference = second[second_index] - second[second_index - 1];
        if (compare(second_difference, first_difference)) {
            result[result_index] = result[result_index - 1] + second_difference;
            second_index++;
        } else {
            result[result_index] = result[result_index - 1] + first_difference;
            first_index++;
        }
        result_index++;
    }
    while (first_index < first_size) {
        T difference = first[first_index] - first[first_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        first_index++;
        result_index++;
    }
    while (second_index < second_size) {
        T difference = second[second_index] - second[second_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        second_index++;
        result_index++;
    }
    return result;
}

template <class T, class Compare>
std::vector<T> linear_structured_convolution_with_infinity(
    const std::vector<T>& first, const std::vector<T>& second,
    const T& infinity, Compare compare) {
    if (first.empty() || second.empty()) return {};

    auto [first_left, first_right] = finite_interval(first, infinity);
    auto [second_left, second_right] = finite_interval(second, infinity);
    int result_size = int(first.size() + second.size() - 1);
    std::vector<T> result(result_size, infinity);
    if (first_left == first_right || second_left == second_right) return result;

    int offset = first_left + second_left;
    result[offset] = first[first_left] + second[second_left];

    int first_index = first_left + 1;
    int second_index = second_left + 1;
    int result_index = offset + 1;
    while (first_index < first_right && second_index < second_right) {
        T first_difference = first[first_index] - first[first_index - 1];
        T second_difference = second[second_index] - second[second_index - 1];
        if (compare(second_difference, first_difference)) {
            result[result_index] = result[result_index - 1] + second_difference;
            second_index++;
        } else {
            result[result_index] = result[result_index - 1] + first_difference;
            first_index++;
        }
        result_index++;
    }
    while (first_index < first_right) {
        T difference = first[first_index] - first[first_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        first_index++;
        result_index++;
    }
    while (second_index < second_right) {
        T difference = second[second_index] - second[second_index - 1];
        result[result_index] = result[result_index - 1] + difference;
        second_index++;
        result_index++;
    }
    return result;
}

template <class T, class Compare>
bool is_structured_sequence_with_infinity(const std::vector<T>& sequence,
                                          const T& infinity, Compare violation) {
    auto [left, right] = finite_interval(sequence, infinity);
    for (int i = left; i < right; i++) {
        if (sequence[i] == infinity) return false;
    }
    for (int i = left + 1; i + 1 < right; i++) {
        T first_difference = sequence[i] - sequence[i - 1];
        T second_difference = sequence[i + 1] - sequence[i];
        if (violation(first_difference, second_difference)) return false;
    }
    return true;
}

}  // namespace convolution_detail

template <class T>
bool is_convex_sequence(const std::vector<T>& sequence) {
    for (int i = 1; i + 1 < int(sequence.size()); i++) {
        if (sequence[i] - sequence[i - 1] > sequence[i + 1] - sequence[i]) {
            return false;
        }
    }
    return true;
}

template <class T>
bool is_convex_sequence(const std::vector<T>& sequence, const T& infinity) {
    return convolution_detail::is_structured_sequence_with_infinity(
        sequence, infinity, std::greater<>());
}

template <class T>
bool is_concave_sequence(const std::vector<T>& sequence) {
    for (int i = 1; i + 1 < int(sequence.size()); i++) {
        if (sequence[i] - sequence[i - 1] < sequence[i + 1] - sequence[i]) {
            return false;
        }
    }
    return true;
}

template <class T>
bool is_concave_sequence(const std::vector<T>& sequence,
                         const T& negative_infinity) {
    return convolution_detail::is_structured_sequence_with_infinity(
        sequence, negative_infinity, std::less<>());
}

template <class T>
std::vector<T> min_plus_convolution_convex(const std::vector<T>& arbitrary,
                                           const std::vector<T>& convex) {
    auto add = [](const T& first, const T& second) { return first + second; };
    return convolution_detail::structured_convolution(arbitrary, convex,
                                                      std::less<>(), add);
}

template <class T>
std::vector<T> min_plus_convolution_convex(const std::vector<T>& arbitrary,
                                           const std::vector<T>& convex,
                                           const T& infinity) {
    return convolution_detail::structured_convolution_with_infinity(
        arbitrary, convex, infinity, std::less<>());
}

template <class T>
std::vector<T> min_plus_convolution_convex_convex(const std::vector<T>& first,
                                                  const std::vector<T>& second) {
    return convolution_detail::linear_structured_convolution(first, second, std::less<>());
}

template <class T>
std::vector<T> min_plus_convolution_convex_convex(
    const std::vector<T>& first, const std::vector<T>& second,
    const T& infinity) {
    return convolution_detail::linear_structured_convolution_with_infinity(
        first, second, infinity, std::less<>());
}

template <class T>
std::vector<T> max_plus_convolution_concave(const std::vector<T>& arbitrary,
                                            const std::vector<T>& concave) {
    auto add = [](const T& first, const T& second) { return first + second; };
    return convolution_detail::structured_convolution(arbitrary, concave,
                                                      std::greater<>(), add);
}

template <class T>
std::vector<T> max_plus_convolution_concave(const std::vector<T>& arbitrary,
                                            const std::vector<T>& concave,
                                            const T& negative_infinity) {
    return convolution_detail::structured_convolution_with_infinity(
        arbitrary, concave, negative_infinity, std::greater<>());
}

template <class T>
std::vector<T> max_plus_convolution_concave_concave(const std::vector<T>& first,
                                                    const std::vector<T>& second) {
    return convolution_detail::linear_structured_convolution(first, second, std::greater<>());
}

template <class T>
std::vector<T> max_plus_convolution_concave_concave(
    const std::vector<T>& first, const std::vector<T>& second,
    const T& negative_infinity) {
    return convolution_detail::linear_structured_convolution_with_infinity(
        first, second, negative_infinity, std::greater<>());
}

}  // namespace convex
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Structured Min-Plus and Max-Plus Convolution
(convex/monge/min_plus_convolution.hpp)

Overview

Functions

Complexity

Example

Depends on

Required by

Verified with

Code

Structured Min-Plus and Max-Plus Convolution (convex/monge/min_plus_convolution.hpp)

Overview

Functions

Complexity

Example

Depends on

Required by

Verified with

Code

Structured Min-Plus and Max-Plus Convolution
(convex/monge/min_plus_convolution.hpp)