Skip to main content

library_checker/data_structure/
static_range_sum_with_upper_bound.rs

1use competitive::prelude::*;
2use competitive::{
3    algebra::AdditiveOperation,
4    data_structure::{RangeFoldWithUpperBound, WaveletMatrix},
5};
6
7#[verify::library_checker("static_range_sum_with_upper_bound")]
8pub fn static_range_sum_with_upper_bound(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, q, a: [u32; iter n]);
11    type M = (AdditiveOperation<i64>, AdditiveOperation<i64>);
12    let mut fold: RangeFoldWithUpperBound<_, M> =
13        RangeFoldWithUpperBound::new(a.map(|a| (a, (1, i64::from(a)))));
14    for _ in 0..q {
15        sc!(l, r, x: u32);
16        fold.query(l..r, x);
17    }
18    pp!(@ittup fold.execute());
19}
20
21#[verify::library_checker("static_range_sum_with_upper_bound")]
22pub fn static_range_sum_with_upper_bound_wavelet_matrix(reader: impl Read, writer: impl Write) {
23    prepare_io!(reader, writer);
24    sc!(n, q, a: [i64; n]);
25    let weights = a.clone();
26    let wm = WaveletMatrix::new(a);
27    let fold = wm.build_fold::<AdditiveOperation<i64>>(&weights);
28    for _ in 0..q {
29        sc!(l, r, x: i64);
30        let (count, sum) = fold.fold_lessthan_with_count(x + 1, l..r);
31        pp!(count, sum);
32    }
33}