haar_lib/ds/
static_range_count_query.rs

1//! 種類数クエリ
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/static_range_count_distinct>
5//! - <https://atcoder.jp/contests/abc174/tasks/abc174_f>
6
7use crate::algo::bsearch_slice::BinarySearch;
8use crate::ds::fenwick_add::FenwickTreeAdd;
9
10/// 種類数クエリ
11pub struct StaticRangeCountQuery {
12    data: Vec<usize>,
13    qs: Vec<(usize, usize, usize)>,
14}
15
16impl StaticRangeCountQuery {
17    /// 配列`a`から`StaticRangeCountQuery`を作る。
18    pub fn new<T: Clone + Ord>(a: Vec<T>) -> Self {
19        let mut temp = a.clone();
20        temp.sort();
21        temp.dedup();
22
23        let data = a.into_iter().map(|x| temp.lower_bound(&x)).collect();
24        Self { data, qs: vec![] }
25    }
26
27    /// 範囲`l..r`でのクエリを追加する。
28    pub fn add(&mut self, l: usize, r: usize) {
29        let i = self.qs.len();
30        self.qs.push((r, l, i));
31    }
32
33    /// 種類数クエリを解く。
34    pub fn solve(mut self) -> Vec<usize> {
35        self.qs.sort();
36        let n = self.data.len();
37        let q = self.qs.len();
38
39        let mut b = FenwickTreeAdd::<usize>::new(n);
40        let mut last_index = vec![!0; n];
41        let mut ret = vec![0; q];
42        let mut cur = 0;
43
44        for (r, l, i) in self.qs {
45            while cur < r {
46                if last_index[self.data[cur]] != !0 {
47                    b.sub(last_index[self.data[cur]], 1);
48                }
49
50                last_index[self.data[cur]] = cur;
51                b.add(last_index[self.data[cur]], 1);
52
53                cur += 1;
54            }
55
56            ret[i] = b.fold(l..r);
57        }
58
59        ret
60    }
61}
haar_lib/ds/static_range_count_query.rs

haar_lib/ds/
static_range_count_query.rs
