Monotone Minima
(Algorithm/monotoneminima.hpp)

• View this file on GitHub
• Last update: 2022-02-05 01:38:09+09:00
• Include: #include "Algorithm/monotoneminima.hpp"

使い方

vector<int> MonotoneMinima(int R,int C,function<bool(int,int,int)> f): $R \times C$ 行列の各行で最小値を取る列の index を返す。
$f(i,j,k)$ は $A_{i,j}$ と $A_{i,k}$ を比較して、 $A_{i,j}$ を採用するなら false ( $A_{i,k}$ を採用するなら true ) を返す関数。

Required by

• Convex Min Plus Convolution (Convolution/convexminplus.hpp)

Code

#pragma once

template<typename F>vector<int> MonotoneMinima(int R,int C,F cmp){
    // cmp(i,j,k) := compare A[i,j] and A[i,k] (A[i,j] -> false, A[i,k] -> true)

    vector<int> ret(R);
    auto rec=[&](auto& f,vector<int> target)->void{
        int m=target.size();
        if(m==0)return;
        vector<int> even;
        for(int i=1;i<m;i+=2)even.push_back(target[i]);
        f(f,even);
        int cur=0;
        for(int i=0;i<m;i+=2){
            ret[target[i]]=cur;
            int end=C-1;
            if(i!=m-1)end=ret[even[i/2]];
            while(cur<end){
                cur++;
                if(cmp(target[i],ret[target[i]],cur))ret[target[i]]=cur;
            }
        }
    };
    vector<int> tmp(R);
    iota(ALL(tmp),0);
    rec(rec,tmp);
    return ret;
}

/**
 * @brief Monotone Minima
 * @docs docs/monotoneminima.md
 */

#line 2 "Algorithm/monotoneminima.hpp"

template<typename F>vector<int> MonotoneMinima(int R,int C,F cmp){
    // cmp(i,j,k) := compare A[i,j] and A[i,k] (A[i,j] -> false, A[i,k] -> true)

    vector<int> ret(R);
    auto rec=[&](auto& f,vector<int> target)->void{
        int m=target.size();
        if(m==0)return;
        vector<int> even;
        for(int i=1;i<m;i+=2)even.push_back(target[i]);
        f(f,even);
        int cur=0;
        for(int i=0;i<m;i+=2){
            ret[target[i]]=cur;
            int end=C-1;
            if(i!=m-1)end=ret[even[i/2]];
            while(cur<end){
                cur++;
                if(cmp(target[i],ret[target[i]],cur))ret[target[i]]=cur;
            }
        }
    };
    vector<int> tmp(R);
    iota(ALL(tmp),0);
    rec(rec,tmp);
    return ret;
}

/**
 * @brief Monotone Minima
 * @docs docs/monotoneminima.md
 */

Back to top page