Struct RangeFoldWithUpperBound 

pub struct RangeFoldWithUpperBound<K, M>
where
    M: AbelianGroup,
{
    keys: Vec<K>,
    weights: Vec<M::T>,
    queries: Vec<(Range<usize>, K)>,
}

Offline range folds over entries whose keys are at most a query bound.

Fields

keys: Vec<K>

weights: Vec<M::T>

queries: Vec<(Range<usize>, K)>

Implementations

impl<K, M> RangeFoldWithUpperBound<K, M>

where K: RadixSortKey + Ord, M: AbelianGroup,

pub fn new(values: impl IntoIterator<Item = (K, M::T)>) -> Self

Examples found in repository

crates/library_checker/src/data_structure/static_range_sum_with_upper_bound.rs (line 13)

pub fn static_range_sum_with_upper_bound(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u32; iter n]);
    type M = (AdditiveOperation<i64>, AdditiveOperation<i64>);
    let mut fold: RangeFoldWithUpperBound<_, M> =
        RangeFoldWithUpperBound::new(a.map(|a| (a, (1, i64::from(a)))));
    for _ in 0..q {
        sc!(l, r, x: u32);
        fold.query(l..r, x);
    }
    pp!(@ittup fold.execute());
}

pub fn query(&mut self, range: Range<usize>, upper_bound: K) -> usize

Examples found in repository

crates/library_checker/src/data_structure/static_range_sum_with_upper_bound.rs (line 16)

pub fn static_range_sum_with_upper_bound(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u32; iter n]);
    type M = (AdditiveOperation<i64>, AdditiveOperation<i64>);
    let mut fold: RangeFoldWithUpperBound<_, M> =
        RangeFoldWithUpperBound::new(a.map(|a| (a, (1, i64::from(a)))));
    for _ in 0..q {
        sc!(l, r, x: u32);
        fold.query(l..r, x);
    }
    pp!(@ittup fold.execute());
}

pub fn execute(self) -> Vec<M::T>

Examples found in repository

crates/library_checker/src/data_structure/static_range_sum_with_upper_bound.rs (line 18)

pub fn static_range_sum_with_upper_bound(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, a: [u32; iter n]);
    type M = (AdditiveOperation<i64>, AdditiveOperation<i64>);
    let mut fold: RangeFoldWithUpperBound<_, M> =
        RangeFoldWithUpperBound::new(a.map(|a| (a, (1, i64::from(a)))));
    for _ in 0..q {
        sc!(l, r, x: u32);
        fold.query(l..r, x);
    }
    pp!(@ittup fold.execute());
}