Monotone 行最小値問題 (Monotone Minima, in O(H + W log H))
(Optimization/monotone_minima.hpp)

• View this file on GitHub
• Last update: 2026-11-12 11:56:29+09:00
• Include: #include "Optimization/monotone_minima.hpp"

概要

$H \times W$ 行列 $A$ が Monotone であるとき、 計算量 $O(H + W \log H)$ で、$A$ の各行に対する最小値を求める。

仕様

template<class VAL, class FUNC> vector<pair<VAL, int>> MonotoneMinima(int H, int W, const FUNC &f)

• $H \times W$ 行列の $(i, j)$ 成分が $f(i, j)$ で表されるとする
• 返り値: 受け取る変数を res として
  • res[l].first: $l$ 行目の最小値
  • res[l].second: $l$ 行目の値が最小となる列の番号

問題例

• COLOCON 2018 Final C - スペースエクスプローラー高橋君

参考文献

• tatyam: Monge の手引き書

Required by

• Monge 単一始点 d-辺最短路問題 (by Alien DP) (Optimization/alien_dp.hpp)
• Monotone 単一始点最短路問題 (D&D Monotone Minima, in O(N (log N)^2)) (Optimization/dd_monotone_minima.hpp)
• Monge 全部乗せ (Optimization/monge_all.hpp)
• Monge 単一始点 d-辺最短路の d = 1, 2, ..., D における列挙 (Optimization/monge_enum_d_shortest_paths.hpp)
• Monge 単一始点最短路アルゴリズム群のラッパー (Optimization/monge_shortest_path.hpp)

Verified with

• tests/yukicoder/yukicoder_0409_monge_shortest_path_simple_larsch.test.cpp
• tests/yukicoder/yukicoder_0705_dd_monotone_minima.test.cpp
• tests/yukicoder/yukicoder_0705_monge_shortest_path.test.cpp
• tests/yukicoder/yukicoder_0952_monge_d_enum_shortest_path.test.cpp
• tests/yukicoder/yukicoder_2078_monge_shortest_path_simple_larsch.test.cpp
• tests/AtCoder/ABC_218_H_alien_dp.cpp (manual)
• tests/AtCoder/EDPC_Z_dd_monotone_minima.cpp (manual)
• tests/AtCoder/colopl2018-final_C_monotone_minima.cpp (manual)
• tests/Codeforces/Codeforces_Round_189_Div1_C_dd_monotone_minima.cpp (manual)
• tests/Codeforces/Codeforces_Round_438_Div12_F_alien_dp.cpp (manual)
• tests/Codeforces/Codeforces_Round_438_Div12_F_d_enum_sliding_monotone_minima.cpp (manual)
• tests/Others/MOFE_monoxercon_202508_K.cpp (manual)

Code

#pragma once
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

// find min_j f(i, j) for all i, by Monotone Minima, O(H + W log H)
// f(i, j) must be monotone (argmin is not decreasing)
// slide access OK
template<class VAL, class FUNC> void MonotoneMinimaRec
(int HL, int HR, int WL, int WR, const FUNC &f, vector<pair<VAL, int>> &res) {
    if (HR - HL <= 0) return;
    int HM = (HL + HR) / 2;
    res[HM].second = WL;
    for (int i = WL; i < WR; i++) {
        VAL val = f(HM, i);
        if (res[HM].first > val) res[HM] = make_pair(val, i);
    }
    MonotoneMinimaRec(HL, HM, WL, res[HM].second + 1, f, res);
    MonotoneMinimaRec(HM + 1, HR, res[HM].second, WR, f, res);
}
template<class VAL, class FUNC> vector<pair<VAL, int>> MonotoneMinima(int H, int W, const FUNC &f) {
    vector<pair<VAL, int>> res(H, make_pair(numeric_limits<VAL>::max() / 2, -1));
    MonotoneMinimaRec(0, H, 0, W, f, res);
    return res;
}

#line 2 "Optimization/monotone_minima.hpp"
#include <bits/stdc++.h>
#line 4 "Optimization/monotone_minima.hpp"
using namespace std;

// find min_j f(i, j) for all i, by Monotone Minima, O(H + W log H)
// f(i, j) must be monotone (argmin is not decreasing)
// slide access OK
template<class VAL, class FUNC> void MonotoneMinimaRec
(int HL, int HR, int WL, int WR, const FUNC &f, vector<pair<VAL, int>> &res) {
    if (HR - HL <= 0) return;
    int HM = (HL + HR) / 2;
    res[HM].second = WL;
    for (int i = WL; i < WR; i++) {
        VAL val = f(HM, i);
        if (res[HM].first > val) res[HM] = make_pair(val, i);
    }
    MonotoneMinimaRec(HL, HM, WL, res[HM].second + 1, f, res);
    MonotoneMinimaRec(HM + 1, HR, res[HM].second, WR, f, res);
}
template<class VAL, class FUNC> vector<pair<VAL, int>> MonotoneMinima(int H, int W, const FUNC &f) {
    vector<pair<VAL, int>> res(H, make_pair(numeric_limits<VAL>::max() / 2, -1));
    MonotoneMinimaRec(0, H, 0, W, f, res);
    return res;
}

Back to top page