n1_rmq/
lib.rs

1pub struct N1Rmq<T> {
2    base: Vec<T>,
3    large: SparseTable<T>,
4    small: Vec<u8>,
5    types: Vec<usize>,
6    b: usize,
7}
8
9impl<T: Clone + Ord> From<Vec<T>> for N1Rmq<T> {
10    fn from(base: Vec<T>) -> Self {
11        let n = base.len();
12        let lg_n = n.next_power_of_two().trailing_zeros();
13        let b = 1.max(lg_n / 4) as usize;
14
15        let mut large = vec![];
16        let mut small = vec![0; (b * b) << (2 * b)];
17        let mut types = vec![];
18        let mut seen = vec![false; 1 << (2 * b)];
19        for ch in base.chunks(b) {
20            large.push(ch.iter().min().unwrap().clone());
21            let ty = enc(ch);
22            types.push(ty);
23            if !seen[ty] {
24                for l in 0..ch.len() {
25                    let mut j = l;
26                    for r in l..ch.len() {
27                        if ch[j] > ch[r] {
28                            j = r;
29                        }
30                        let i = (ty * b + l) * b + r;
31                        small[i] = j as _;
32                    }
33                }
34                seen[ty] = true;
35            }
36        }
37        let large: SparseTable<_> = large.into();
38        Self { base, large, small, types, b }
39    }
40}
41
42impl<T: Clone + Ord> N1Rmq<T> {
43    fn index(&self, bucket: usize, start: usize, end: usize) -> usize {
44        let b = self.b;
45        (self.types[bucket] * b + start) * b + end
46    }
47
48    pub fn min(&self, l: usize, r: usize) -> &T {
49        assert!(l < r);
50        let b = self.b;
51        let lb = l / b;
52        let rb = (r - 1) / b;
53        if lb == rb {
54            let j = self.small[self.index(lb, l % b, (r - 1) % b)] as usize;
55            return &self.base[lb * b + j];
56        }
57        let mut res = if l % b == 0 {
58            self.large.min(lb, lb + 1)
59        } else {
60            let j = self.small[self.index(lb, l % b, b - 1)] as usize;
61            &self.base[lb * b + j]
62        };
63        res = res.min(if r % b == 0 {
64            self.large.min(rb, rb + 1)
65        } else {
66            let j = self.small[self.index(rb, 0, (r - 1) % b)] as usize;
67            &self.base[rb * b + j]
68        });
69
70        if lb + 1 < rb {
71            res = res.min(self.large.min(lb + 1, rb));
72        }
73        res
74    }
75}
76
77fn enc<T: Ord>(a: &[T]) -> usize {
78    let mut stack = vec![];
79    let mut res = 0;
80    for ai in a {
81        while let Some(&last) = stack.last() {
82            if last > ai {
83                stack.pop();
84                res = res << 1 | 1;
85            } else {
86                break;
87            }
88        }
89        stack.push(ai);
90        res = res << 1 | 0;
91    }
92    ((res + 1) << stack.len()) - 1
93}
94
95struct SparseTable<T> {
96    base: Vec<T>,
97    table: Vec<Vec<usize>>,
98}
99
100impl<T: Ord> From<Vec<T>> for SparseTable<T> {
101    fn from(base: Vec<T>) -> Self {
102        let mut table = vec![];
103        let n = base.len();
104        table.push((0..n).collect::<Vec<_>>());
105        for sh in 1.. {
106            let last = table.last().unwrap();
107            let len = 1 << sh;
108            if len >= n {
109                break;
110            }
111            let mut cur = vec![0; n - len + 1];
112            for i in len..=n {
113                let (il, ir) = (last[i - len], last[i - len + (1 << (sh - 1))]);
114                cur[i - len] = if base[il] < base[ir] { il } else { ir };
115            }
116            table.push(cur);
117        }
118        Self { base, table }
119    }
120}
121
122impl<T: Ord> SparseTable<T> {
123    pub fn min(&self, i: usize, j: usize) -> &T {
124        let len = j - i;
125        if len <= 1 {
126            return &self.base[i];
127        }
128        let sh = len.next_power_of_two().trailing_zeros() as usize - 1;
129        let [il, ir] = [self.table[sh][i], self.table[sh][j - (1 << sh)]];
130        (&self.base[il]).min(&self.base[ir])
131    }
132}
133
134#[test]
135fn test() {
136    let n = 20000;
137    let it = std::iter::successors(Some(3_usize), |x| Some(3 * x % 46337));
138    let a: Vec<_> = it.take(n).collect();
139    let rmq: N1Rmq<_> = a.clone().into();
140
141    for l in 0..n {
142        let mut min = a[l];
143        for r in l..n - 1 {
144            min = min.min(a[r]);
145            assert_eq!(rmq.min(l, r + 1), &min);
146        }
147    }
148}
n1_rmq/lib.rs

n1_rmq/
lib.rs
