Skip to main content

library_checker/data_structure/
range_kth_smallest.rs

1use competitive::data_structure::WaveletMatrix;
2use competitive::prelude::*;
3
4#[verify::library_checker("range_kth_smallest")]
5pub fn range_kth_smallest(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, q, a: [usize; n], queries: [(usize, usize, usize); iter q]);
8    let wm = WaveletMatrix::new(a);
9    let results = wm.quantile_batch(queries.map(|(l, r, k)| (l..r, k)));
10    pp!(@lf @it results);
11}