Trait nekolib::traits::fold_bisect::FoldBisect
source · pub trait FoldBisect: Fold<Range<usize>> {
// Required method
fn fold_bisect<F>(
&self,
l: usize,
pred: F
) -> (usize, <Self::Output as Magma>::Set)
where F: Fn(&<Self::Output as Magma>::Set) -> bool;
}Expand description
左端を固定したときの境界を求める。
Required Methods§
sourcefn fold_bisect<F>(
&self,
l: usize,
pred: F
) -> (usize, <Self::Output as Magma>::Set)where
F: Fn(&<Self::Output as Magma>::Set) -> bool,
fn fold_bisect<F>( &self, l: usize, pred: F ) -> (usize, <Self::Output as Magma>::Set)where F: Fn(&<Self::Output as Magma>::Set) -> bool,
添字 l と述語 pred を引数に取り、次の条件を満たす r を返す。
ただし、区間長を n とする。
pred(&self.fold(l..r))r == n || !pred(&self.fold(l..r + 1))
Requirements
対象のモノイドの単位元を e とするとき、 pred(e) が成り立つ。
Examples
use nekolib::ds::VecSegtree;
use nekolib::traits::{Fold, FoldBisect};
use nekolib::utils::OpAdd;
let vs: VecSegtree<OpAdd<i32>> = vec![2, 4, 1, 3, 5].into();
assert_eq!(vs.fold_bisect(1, |&x| x < 4), (1_usize, 0));
assert_eq!(vs.fold_bisect(1, |&x| x <= 4), (2_usize, 4));
assert_eq!(vs.fold_bisect(1, |&x| x < 13), (4_usize, 8));
assert_eq!(vs.fold_bisect(1, |&x| x <= 13), (5_usize, 13));
let l = 1;
let pred = |&x: &i32| x <= 12;
let (r, x) = vs.fold_bisect(l, pred);
assert_eq!(vs.fold(l..r), x);
assert!(pred(&x));
assert!(r == vs.len() || !pred(&vs.fold(l..r + 1)));