math/concave_max_plus_convolution.hpp

#include"../DP/monotone_minima.hpp"
vector<lint> concave_max_plus_convolution(const vector<lint>& a,const vec& b){
    auto f=[&](lint i,lint j){
        if(i-j<0||(int)a.size()<=j||(int)b.size()<=i-j)return INF;
        else return -(a[j]+b[i-j]);
    };
    auto v=monotone_minima(a.size()+b.size()-1,b.size(),INF,f);
    output(v);
    vec res((int)a.size()+(int)b.size()-1);
    rep(i,a.size()+b.size()-1){
        res[i]=-f(i,v[i]);
    }
    return res;
};

#line 1 "DP/monotone_minima.hpp"
//monotoneな二変数関数に対して各行の最小値を求める
template<typename T,typename F>
vector<int> monotone_minima(int h,int w,T inf,F f){
    vector<int>ret(h);
    auto g=[&](auto g,int a,int b,int c,int d,T inf,auto f)->void{
        int e=(a+b)/2,idx=0;
        T mn=inf;
        for(int i=c;i<d;++i){
            if(mn>f(e,i))mn=f(e,i),idx=i;
        }
        ret[e]=idx;
        if(b>a+1){
            g(g,a,e,c,idx+1,inf,f);
            g(g,e,b,idx,d,inf,f);
        }
    };
    g(g,0,h,0,w,inf,f);
    return ret;
}
#line 2 "math/concave_max_plus_convolution.hpp"
vector<lint> concave_max_plus_convolution(const vector<lint>& a,const vec& b){
    auto f=[&](lint i,lint j){
        if(i-j<0||(int)a.size()<=j||(int)b.size()<=i-j)return INF;
        else return -(a[j]+b[i-j]);
    };
    auto v=monotone_minima(a.size()+b.size()-1,b.size(),INF,f);
    output(v);
    vec res((int)a.size()+(int)b.size()-1);
    rep(i,a.size()+b.size()-1){
        res[i]=-f(i,v[i]);
    }
    return res;
};