sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "convolution/convex_min_plus_convolution.hpp"
数列 $a$ と上に凸な数列 $b$ の min-plus convolution $c_i=\min_j {a_j + b_{i-j}}$ を求める.
vector<T> convex_min_plus_convolution(vector<T> a, vector<T> b)
vector<T> concave_max_plus_convolution(vector<T> a, vector<T> b)
#pragma once #include <limits> #include <vector> #include "../dp/monotone_minima.hpp" // b is convex template <typename T> std::vector<T> convex_min_plus_convolution(const std::vector<T>& a, const std::vector<T>& b) { int len = a.size() + b.size() - 1; auto f = [&](int i, int j) { if (i - j < 0 || (int)b.size() <= i - j) return std::numeric_limits<T>::max(); return a[j] + b[i - j]; }; auto idx = monotone_minima(len, a.size(), f); std::vector<T> res(len); for (int i = 0; i < len; ++i) res[i] = f(i, idx[i]); return res; } // b is concave template <typename T> std::vector<T> concave_max_plus_convolution(std::vector<T> a, std::vector<T> b) { for (auto& x : a) x = -x; for (auto& x : b) x = -x; auto c = convex_min_plus_convolution(a, b); for (auto& x : c) x = -x; return c; }
#line 2 "convolution/convex_min_plus_convolution.hpp" #include <limits> #include <vector> #line 3 "dp/monotone_minima.hpp" template <typename F> std::vector<int> monotone_minima(int n, int m, const F& f) { std::vector<int> idx(n, -1); auto calc = [&](const auto& calc, int l, int r, int optl, int optr) -> void { if (l > r) return; int m = std::midpoint(l, r); auto mi = f(m, optl); idx[m] = optl; for (int i = optl + 1; i <= optr; ++i) { auto v = f(m, i); if (mi > v) { mi = v; idx[m] = i; } } calc(calc, l, m - 1, optl, idx[m]); calc(calc, m + 1, r, idx[m], optr); }; calc(calc, 0, n - 1, 0, m - 1); return idx; } #line 5 "convolution/convex_min_plus_convolution.hpp" // b is convex template <typename T> std::vector<T> convex_min_plus_convolution(const std::vector<T>& a, const std::vector<T>& b) { int len = a.size() + b.size() - 1; auto f = [&](int i, int j) { if (i - j < 0 || (int)b.size() <= i - j) return std::numeric_limits<T>::max(); return a[j] + b[i - j]; }; auto idx = monotone_minima(len, a.size(), f); std::vector<T> res(len); for (int i = 0; i < len; ++i) res[i] = f(i, idx[i]); return res; } // b is concave template <typename T> std::vector<T> concave_max_plus_convolution(std::vector<T> a, std::vector<T> b) { for (auto& x : a) x = -x; for (auto& x : b) x = -x; auto c = convex_min_plus_convolution(a, b); for (auto& x : c) x = -x; return c; }