nekolib/ds/
n1_rmq.rs

1//! 線形 RMQ。
2
3/// $\\langle O(n), O(1)\\rangle$ RMQ。
4///
5/// # Idea
6/// 簡潔データ構造の文脈でよくあるように、配列を数個ずつの要素からなるブロックに区切り、
7/// 各ブロック内では表引きを行う。ここでは特に簡潔の実装にはしていないことに注意。
8///
9/// ブロックサイズは $b = \\frac{1}{4}\\log\_2(n)$ とする。
10/// ブロック内の最小値たちを、$\\langle O(n\\log(n)), O(1)\\rangle$ の RMQ である sparse table
11/// で管理する。$O(n/\\log(n)\\cdot \\log(n/\\log(n))) = O(n)$ なので ok。
12///
13/// $b = \\frac{1}{4}\\log\_2(n)$ サイズの小ブロックたちについて、それらの argmin
14/// を表引きすることを考える。Cartesian tree を考えると、argmin のテーブルは $2^{2b} = \\sqrt{n}$
15/// 種類しかないことがわかる。よって、各種類ごとに愚直に求めても $O(\\sqrt{n}\\,\\log(n)^2)$
16/// 時間なので、こちらも ok。
17pub struct N1Rmq<T> {
18    base: Vec<T>,
19    large: SparseTable<T>,
20    small: Vec<u8>,
21    types: Vec<usize>,
22    b: usize,
23}
24
25impl<T: Clone + Ord> From<Vec<T>> for N1Rmq<T> {
26    fn from(base: Vec<T>) -> Self {
27        let n = base.len();
28        let lg_n = n.next_power_of_two().trailing_zeros();
29        let b = 1.max(lg_n / 4) as usize;
30
31        let mut large = vec![];
32        let mut small = vec![0; (1 << (2 * b)) * b * b];
33        let mut types = vec![];
34        let mut seen = vec![false; 1 << (2 * b)];
35        for ch in base.chunks(b) {
36            large.push(ch.iter().min().unwrap().clone());
37            let ty = cartesian_tree(ch);
38            types.push(ty);
39            if !seen[ty] {
40                for l in 0..ch.len() {
41                    let mut j = l;
42                    for r in l..ch.len() {
43                        if ch[j] > ch[r] {
44                            j = r;
45                        }
46                        let i = (ty * b + l) * b + r;
47                        small[i] = j as u8;
48                    }
49                }
50                seen[ty] = true;
51            }
52        }
53        let large: SparseTable<_> = large.into();
54        Self { base, large, small, types, b }
55    }
56}
57
58impl<T: Clone + Ord> N1Rmq<T> {
59    fn index(&self, bucket: usize, start: usize, end: usize) -> usize {
60        let b = self.b;
61        (self.types[bucket] * b + start) * b + end
62    }
63
64    pub fn min(&self, l: usize, r: usize) -> &T {
65        let b = self.b;
66        let lb = l / b;
67        let rb = (r - 1) / b;
68        if lb == rb {
69            let j = self.small[self.index(lb, l % b, (r - 1) % b)] as usize;
70            return &self.base[lb * b + j];
71        }
72
73        let mut res = if l % b == 0 {
74            self.large.min(lb, lb + 1)
75        } else {
76            let j = self.small[self.index(lb, l % b, b - 1)] as usize;
77            &self.base[lb * b + j]
78        };
79
80        res = res.min(if r % b == 0 {
81            self.large.min(rb, rb + 1)
82        } else {
83            let j = self.small[self.index(rb, 0, (r - 1) % b)] as usize;
84            &self.base[rb * b + j]
85        });
86
87        if lb + 1 < rb {
88            res = res.min(self.large.min(lb + 1, rb));
89        }
90
91        res
92    }
93}
94
95fn cartesian_tree<T: Ord>(a: &[T]) -> usize {
96    let mut stack = vec![];
97    let mut res = 1;
98    for ai in a {
99        while let Some(&last) = stack.last() {
100            if last > ai {
101                stack.pop();
102                res <<= 1;
103            } else {
104                break;
105            }
106        }
107        stack.push(ai);
108        res = res << 1 | 1;
109    }
110    res << (stack.len() - 1)
111}
112
113struct SparseTable<T> {
114    base: Vec<T>,
115    table: Vec<Vec<usize>>,
116}
117
118impl<T: Ord> From<Vec<T>> for SparseTable<T> {
119    fn from(base: Vec<T>) -> Self {
120        let mut table = vec![];
121        let n = base.len();
122        table.push((0..n).collect::<Vec<_>>());
123        for sh in 1.. {
124            let last = table.last().unwrap();
125            let len = 1 << sh;
126            if len >= n {
127                break;
128            }
129            let mut cur = vec![0; n - len + 1];
130            for i in len..=n {
131                let (il, ir) = (last[i - len], last[i - len + (1 << (sh - 1))]);
132                cur[i - len] = if base[il] < base[ir] { il } else { ir };
133            }
134            table.push(cur);
135        }
136        Self { base, table }
137    }
138}
139
140impl<T: Ord> SparseTable<T> {
141    pub fn min(&self, i: usize, j: usize) -> &T {
142        let len = j - i;
143        if len <= 1 {
144            return &self.base[i];
145        }
146        let sh = len.next_power_of_two().trailing_zeros() as usize - 1;
147        let [il, ir] = [self.table[sh][i], self.table[sh][j - (1 << sh)]];
148        (&self.base[il]).min(&self.base[ir])
149    }
150}
151
152#[test]
153fn test() {
154    let n = 20000;
155    let it = std::iter::successors(Some(3_usize), |x| Some(3 * x % 46337));
156    let a: Vec<_> = it.take(n).collect();
157    let rmq: N1Rmq<_> = a.clone().into();
158
159    for l in 0..n {
160        let mut min = a[l];
161        for r in l..n - 1 {
162            min = min.min(a[r]);
163            assert_eq!(rmq.min(l, r + 1), &min);
164        }
165    }
166}
nekolib/ds/n1_rmq.rs

nekolib/ds/
n1_rmq.rs
