mmrz's library

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

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

Monotoneな行列における行最小値問題(monotone-minima)
(dp/monotone_minima.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "dp/monotone_minima.hpp"

Monotoneな行列における行最小値問題(monotone-minima)

使い方

• vector<int> monotone_minima(int n, int m, const F &argmin) : $N$ 行 $M$ 列の Monotone な行列について、$i$ 行目の $[l, r)$ 列の $\arg\min$ （最小値の添え字）を求める関数を用意したとき、その行列における各行の最小値の添え字を求める $O(N + \sigma M \log N )$

ただし、 $\sigma$ を $\arg\min$ を求める計算量とする。

概要

$\arg \min_j A_{i,j}$ が $i$ について講義単調増加である時、 $A$ は Monotone であるという。

$A$ が Monotone であれば、 $\arg \min_j A_{i,j}$ が $j$ であると分かったとき、$A_{i, j}$ の右上と左下には $\min_j A_{i, j}$ となる要素が存在しない。よって、分割統治の要領で効率的に最小値を求めることができる。

引数に $A$ を渡してしまった場合、それだけで $O(NM)$ かかることに注意したい。

Verify

スペースエクスプローラー高橋君

参考

Acompany勉強会 2024/06/04 Monge 入門

Code

#pragma once

#include<queue>
#include<tuple>
#include<vector>

// argmin(i,l,r) : argmin_{j\in[l,r)} A[i][j]
template<typename F>
std::vector<int> monotone_minima(int n, int m, const F &argmin){
	std::vector<int> ret(n);

	//submatrix [u, d) * [l, r)
	std::queue<std::tuple<int, int, int, int>> q;
	q.emplace(0, n, 0, m);

	while(not q.empty()){
		auto [u, d, l, r] = q.front();
		q.pop();

		if(u == d)continue;
		int mid = (u+d) >> 1;
		ret[mid] = argmin(mid, l, r);
		q.emplace(u, mid, l, ret[mid]+1);
		q.emplace(mid+1, d, ret[mid], r);
	}

	return ret;
}

#line 2 "dp/monotone_minima.hpp"

#include<queue>
#include<tuple>
#include<vector>

// argmin(i,l,r) : argmin_{j\in[l,r)} A[i][j]
template<typename F>
std::vector<int> monotone_minima(int n, int m, const F &argmin){
	std::vector<int> ret(n);

	//submatrix [u, d) * [l, r)
	std::queue<std::tuple<int, int, int, int>> q;
	q.emplace(0, n, 0, m);

	while(not q.empty()){
		auto [u, d, l, r] = q.front();
		q.pop();

		if(u == d)continue;
		int mid = (u+d) >> 1;
		ret[mid] = argmin(mid, l, r);
		q.emplace(u, mid, l, ret[mid]+1);
		q.emplace(mid+1, d, ret[mid], r);
	}

	return ret;
}

Back to top page