library_checker/data_structure/
static_range_sum_with_upper_bound.rs1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{algebra::AdditiveOperation, data_structure::WaveletMatrix};
4
5#[verify::library_checker("static_range_sum_with_upper_bound")]
6pub fn static_range_sum_with_upper_bound(reader: impl Read, mut writer: impl Write) {
7 let s = read_all_unchecked(reader);
8 let mut scanner = Scanner::new(&s);
9 scan!(scanner, n, q, a: [i64; n]);
10 let weights = a.clone();
11 let wm = WaveletMatrix::new(a);
12 let fold = wm.build_fold::<AdditiveOperation<i64>>(&weights);
13 for _ in 0..q {
14 scan!(scanner, l, r, x: i64);
15 let (count, sum) = fold.fold_lessthan_with_count(x + 1, l..r);
16 writeln!(writer, "{} {}", count, sum).ok();
17 }
18}