Skip to main content

library_checker/data_structure/
static_range_count_distinct.rs

1use competitive::data_structure::{DaryPrefixSumTreeU32, FibHashMap};
2use competitive::prelude::*;
3
4#[verify::library_checker("static_range_count_distinct")]
5pub fn static_range_count_distinct(reader: impl Read, writer: impl Write) {
6    prepare_io!(buffered; reader, writer);
7    sc!(n, q, a: [u32; n], queries: [(usize, usize); q]);
8    let end = queries.iter().map(|&(_, r)| r).max().unwrap_or(0);
9    if end == 0 {
10        pp!(@lf @it std::iter::repeat_n(0u32, q));
11        return;
12    }
13    let mut offsets = vec![0; end + 2];
14    for &(_, r) in &queries {
15        offsets[r] += 1;
16    }
17    for r in 0..=end {
18        offsets[r + 1] += offsets[r];
19    }
20    let mut order = vec![(0, 0); q];
21    for (i, (l, r)) in queries.into_iter().enumerate() {
22        offsets[r] -= 1;
23        order[offsets[r]] = (l as u32, i as u32);
24    }
25    let mut bit = DaryPrefixSumTreeU32::new(end + 1);
26    let mut last = FibHashMap::default();
27    let mut ans = vec![0; q];
28    for r in 0..=end {
29        if r != 0 {
30            let previous = last.insert(a[r - 1], r).unwrap_or(0);
31            bit.update(previous, 1);
32        }
33        for &(l, i) in &order[offsets[r]..offsets[r + 1]] {
34            ans[i as usize] = bit.accumulate0(l as usize + 1) - l;
35        }
36    }
37    pp!(@lf @it ans);
38}