haar_lib/algo/
monotone_minima.rs

1//! Monotone minima
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/colopl2018-final/tasks/colopl2018_final_c>
5//! - <https://judge.yosupo.jp/problem/min_plus_convolution_convex_convex>
6
7use crate::chmin;
8
9/// `n`行`m`列の行列の各行の最小値の位置と値を求める。
10///
11/// ただし、$i$番目の行の最小値となる列の位置$a_i$について、$a_0 \le a_1 \le \dots \le a_{n-1}$、を満たしていること。
12///
13/// **Time complexity** $O(n + m \log n)$
14pub fn monotone_minima<T, F>(n: usize, m: usize, a: F) -> Vec<(usize, T)>
15where
16    T: Ord + Clone,
17    F: Fn(usize, usize) -> T,
18{
19    let mut ret = vec![None; n];
20    rec(0, n, 0, m, &a, &mut ret);
21    ret.into_iter().flatten().collect()
22}
23
24fn rec<T, F>(
25    top: usize,
26    bottom: usize,
27    left: usize,
28    right: usize,
29    a: &F,
30    ret: &mut Vec<Option<(usize, T)>>,
31) where
32    T: Ord,
33    F: Fn(usize, usize) -> T,
34{
35    if top >= bottom {
36        return;
37    }
38    if top + 1 == bottom {
39        let i = top;
40
41        let mut index = left;
42        let mut m = a(i, left);
43
44        for j in left + 1..right {
45            if chmin!(m, a(i, j)) {
46                index = j;
47            }
48        }
49
50        ret[i] = Some((index, m));
51        return;
52    }
53
54    let mid = (top + bottom) / 2;
55    rec(mid, mid + 1, left, right, a, ret);
56
57    let min_index = ret[mid].as_ref().unwrap().0;
58    rec(top, mid, left, min_index + 1, a, ret);
59    rec(mid + 1, bottom, min_index, right, a, ret);
60}
haar_lib/algo/monotone_minima.rs

haar_lib/algo/
monotone_minima.rs
