library_checker/datastructure/
range_kth_smallest.rs

1#[doc(no_inline)]
2pub use competitive::data_structure::WaveletMatrix;
3use competitive::prelude::*;
4
5#[verify::library_checker("range_kth_smallest")]
6pub fn range_kth_smallest(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: [usize; n]);
10    let wm = WaveletMatrix::new(a, 30);
11    for (l, r, k) in scanner.iter::<(usize, usize, usize)>().take(q) {
12        writeln!(writer, "{}", wm.quantile(l..r, k)).ok();
13    }
14}