haar_lib/algo/
static_range_mode_query.rs

1//! 最頻値取得クエリ
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/static_range_mode_query>
5
6use crate::{algo::bsearch_slice::BinarySearch, misc::range::range_bounds_to_range};
7use std::ops::RangeBounds;
8
9/// 最頻値取得クエリ
10pub struct StaticRangeModeQuery<T> {
11    d: Vec<T>,
12    b: Vec<usize>,
13    b_index: Vec<usize>,
14    block_size: usize,
15    n: usize,
16    index: Vec<Vec<usize>>,
17    mode: Vec<Vec<usize>>,
18    freq: Vec<Vec<usize>>,
19}
20
21impl<T: Clone + Ord> StaticRangeModeQuery<T> {
22    /// 配列`a`での最頻値クエリを構築する。
23    pub fn new(a: Vec<T>) -> Self {
24        let mut d = a.clone();
25        let n = a.len();
26        let block_size = n.isqrt();
27        let block_num = n.div_ceil(block_size);
28        let mut mode = vec![vec![0; block_num]; block_num];
29        let mut freq = vec![vec![0; block_num]; block_num];
30
31        d.sort();
32        d.dedup();
33        let k = d.len();
34
35        let b = a.iter().map(|x| d.lower_bound(x)).collect::<Vec<_>>();
36
37        let mut index = vec![vec![]; k];
38        let mut b_index = vec![0; n];
39        for i in 0..n {
40            b_index[i] = index[b[i]].len();
41            index[b[i]].push(i);
42        }
43
44        for i in 0..block_num {
45            let mut temp = vec![0; k];
46            let mut md = 0;
47            let mut fr = 0;
48
49            for j in i..block_num {
50                let r = n.min(block_size * (j + 1));
51
52                for x in block_size * j..r {
53                    temp[b[x]] += 1;
54
55                    if temp[b[x]] > fr {
56                        md = b[x];
57                        fr = temp[b[x]];
58                    }
59                }
60
61                mode[i][j] = md;
62                freq[i][j] = fr;
63            }
64        }
65
66        Self {
67            d,
68            b,
69            n,
70            b_index,
71            block_size,
72            index,
73            mode,
74            freq,
75        }
76    }
77
78    /// 範囲`range`での最頻値とその出現回数を返す。
79    pub fn query(&self, range: impl RangeBounds<usize>) -> (T, usize) {
80        let Self {
81            d,
82            b,
83            b_index,
84            block_size,
85            n,
86            index,
87            mode,
88            freq,
89        } = self;
90
91        let (l, r) = range_bounds_to_range(range, 0, *n);
92
93        let mut ret = (None, 0);
94
95        let span_l = l.div_ceil(*block_size);
96        let span_r = r / block_size;
97
98        if span_l < span_r {
99            ret = (
100                Some(d[mode[span_l][span_r - 1]].clone()),
101                freq[span_l][span_r - 1],
102            );
103        }
104
105        // prefix
106        for i in l..r.min(span_l * block_size) {
107            if b_index[i] >= 1 && index[b[i]][b_index[i] - 1] >= l {
108                continue;
109            }
110
111            if b_index[i] + ret.1 < 1
112                || index[b[i]]
113                    .get(b_index[i] + ret.1 - 1)
114                    .is_some_and(|&x| x < r)
115            {
116                let mut fr = ret.1;
117                for j in b_index[i] + ret.1..index[b[i]].len() {
118                    if index[b[i]][j] < r {
119                        fr += 1;
120                    } else {
121                        break;
122                    }
123                }
124
125                if fr > ret.1 {
126                    ret = (Some(d[b[i]].clone()), fr);
127                }
128            }
129        }
130
131        // suffix
132        for i in (l.max(span_r * block_size)..r).rev() {
133            if index[b[i]].get(b_index[i] + 1).is_some_and(|&x| x < r) {
134                continue;
135            }
136
137            if b_index[i] + 1 >= ret.1
138                && index[b[i]]
139                    .get(b_index[i] - ret.1 + 1)
140                    .is_some_and(|&x| x >= l)
141            {
142                let mut fr = ret.1;
143
144                if b_index[i] >= ret.1 {
145                    for j in (0..=self.b_index[i] - ret.1).rev() {
146                        if index[b[i]][j] >= l {
147                            fr += 1;
148                        } else {
149                            break;
150                        }
151                    }
152                }
153
154                if fr > ret.1 {
155                    ret = (Some(d[b[i]].clone()), fr);
156                }
157            }
158        }
159
160        let (m, f) = ret;
161        (m.unwrap(), f)
162    }
163}
haar_lib/algo/static_range_mode_query.rs

haar_lib/algo/
static_range_mode_query.rs
