nekolib/traits/
fold_bisect.rs

1//! 区間和の二分探索に関するトレイトたち。
2//!
3//! 区間のモノイド積が述語を満たすような区間のうち、最大のものを返す。
4
5use super::binop;
6use super::fold;
7
8use std::ops::Range;
9
10use binop::Magma;
11use fold::Fold;
12
13/// 左端を固定したときの境界を求める。
14pub trait FoldBisect: Fold<Range<usize>> {
15    /// 添字 `l` と述語 `pred` を引数に取り、次の条件を満たす `r` を返す。
16    /// ただし、区間長を `n` とする。
17    /// - `pred(&self.fold(l..r))`
18    /// - `r == n || !pred(&self.fold(l..r + 1))`
19    ///
20    /// # Requirements
21    /// 対象のモノイドの単位元を `e` とするとき、 `pred(e)` が成り立つ。
22    ///
23    /// # Examples
24    /// ```
25    /// use nekolib::ds::VecSegtree;
26    /// use nekolib::traits::{Fold, FoldBisect};
27    /// use nekolib::utils::OpAdd;
28    ///
29    /// let vs: VecSegtree<OpAdd<i32>> = vec![2, 4, 1, 3, 5].into();
30    ///
31    /// assert_eq!(vs.fold_bisect(1, |&x| x < 4), (1_usize, 0));
32    /// assert_eq!(vs.fold_bisect(1, |&x| x <= 4), (2_usize, 4));
33    /// assert_eq!(vs.fold_bisect(1, |&x| x < 13), (4_usize, 8));
34    /// assert_eq!(vs.fold_bisect(1, |&x| x <= 13), (5_usize, 13));
35    ///
36    /// let l = 1;
37    /// let pred = |&x: &i32| x <= 12;
38    /// let (r, x) = vs.fold_bisect(l, pred);
39    /// assert_eq!(vs.fold(l..r), x);
40    /// assert!(pred(&x));
41    /// assert!(r == vs.len() || !pred(&vs.fold(l..r + 1)));
42    /// ```
43    fn fold_bisect<F>(
44        &self,
45        l: usize,
46        pred: F,
47    ) -> (usize, <Self::Output as Magma>::Set)
48    where
49        F: Fn(&<Self::Output as Magma>::Set) -> bool;
50}
51
52/// 右端を固定したときの境界を求める。
53pub trait FoldBisectRev: Fold<Range<usize>> {
54    /// 添字 `r` と述語 `pred` を引数に取り、次の条件を満たす `l` を返す。
55    /// - `pred(&self.fold(l..r))`
56    /// - `l == 0 || !pred(&self.fold(l - 1..r))`
57    ///
58    /// # Requirements
59    /// 対象のモノイドの単位元を `e` とするとき、`pred(e)` が成り立つ。
60    ///
61    /// # Examples
62    /// ```
63    /// use nekolib::ds::VecSegtree;
64    /// use nekolib::traits::{Fold, FoldBisectRev};
65    /// use nekolib::utils::OpAdd;
66    ///
67    /// let vs: VecSegtree<OpAdd<i32>> = vec![2, 4, 1, 3, 5].into();
68    ///
69    /// assert_eq!(vs.fold(..), 15);
70    /// assert_eq!(vs.fold_bisect_rev(5, |&x| x <= 0), (5_usize, 0));
71    /// assert_eq!(vs.fold_bisect_rev(5, |&x| x < 15), (1_usize, 13));
72    /// assert_eq!(vs.fold_bisect_rev(5, |&x| x <= 15), (0_usize, 15));
73    ///
74    /// let r = 5;
75    /// let pred = |&x: &i32| x <= 12;
76    /// let (l, x) = vs.fold_bisect_rev(r, pred);
77    /// assert_eq!(vs.fold(l..r), x);
78    /// assert!(pred(&x));
79    /// assert!(l == 0 || !pred(&vs.fold(l - 1..r)));
80    /// ```
81    fn fold_bisect_rev<F>(
82        &self,
83        r: usize,
84        pred: F,
85    ) -> (usize, <Self::Output as Magma>::Set)
86    where
87        F: Fn(&<Self::Output as Magma>::Set) -> bool;
88}
nekolib/traits/fold_bisect.rs

nekolib/traits/
fold_bisect.rs
