library_checker/datastructure/
staticrmq.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::MinOperation,
5    data_structure::{DisjointSparseTable, SegmentTree},
6};
7
8#[verify::library_checker("staticrmq")]
9pub fn staticrmq_disjoint_sparse_table(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
13    let table = DisjointSparseTable::<MinOperation<_>>::new(a);
14    for (l, r) in lr.take(q) {
15        writeln!(writer, "{}", table.fold(l, r)).ok();
16    }
17}
18
19#[verify::library_checker("staticrmq")]
20pub fn staticrmq_segment_tree(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
24    let seg = SegmentTree::<MinOperation<_>>::from_vec(a);
25    for (l, r) in lr.take(q) {
26        writeln!(writer, "{}", seg.fold(l..r)).ok();
27    }
28}