haar_lib/algo/
shakutori.rs

1//! 尺取り法
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc038/tasks/abc038_c>
5//! - <https://atcoder.jp/contests/arc022/tasks/arc022_2>
6
7/// 尺取り法
8///
9/// * remove_left - `|l: usize| {尺取りの左端を縮めたときの操作}`
10/// * can_append_right - `|l: usize, r: usize| {l..r+1が条件を満たすかを判定}`
11/// * append_right - `|r: usize| {尺取りの右端を進めたときの操作}`
12pub fn shakutori(
13    n: usize,
14    mut remove_left: impl FnMut(usize),
15    can_append_right: impl Fn(usize, usize) -> bool,
16    mut append_right: impl FnMut(usize),
17    mut f: impl FnMut(usize, usize),
18) {
19    let mut right = 0;
20
21    for left in 0..n {
22        if right < left {
23            right = left;
24        }
25
26        while right < n {
27            if can_append_right(left, right) {
28                append_right(right);
29                right += 1;
30            } else {
31                break;
32            }
33        }
34
35        f(left, right);
36
37        if left < right {
38            remove_left(left);
39        }
40    }
41}