Skip to main content

library_checker/data_structure/
static_range_frequency.rs

1use competitive::data_structure::{RangeFrequency, WaveletMatrix};
2use competitive::prelude::*;
3
4#[verify::library_checker("static_range_frequency")]
5pub fn static_range_frequency(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, q, a: [u32; n]);
8    let mut range_frequency = RangeFrequency::new(a);
9    for _ in 0..q {
10        sc!(l, r, x: u32);
11        range_frequency.query(l, r, x);
12    }
13    pp!(@lf @it range_frequency.execute());
14}
15
16#[verify::library_checker("static_range_frequency")]
17pub fn static_range_frequency_wavelet_matrix(reader: impl Read, writer: impl Write) {
18    prepare_io!(reader, writer);
19    sc!(n, q, a: [usize; n]);
20    let wm = WaveletMatrix::new(a);
21    for _ in 0..q {
22        sc!(l, r, x: usize);
23        let ans = wm.rank(x, l..r);
24        pp!(ans);
25    }
26}