Struct Doubling

Source

pub struct Doubling<M>where
    M: Monoid,{
    size: usize,
    table: Vec<(usize, M::T)>,
}

Fields§

§size: usize§table: Vec<(usize, M::T)>

Implementations§

Source §

impl<M> Doubling<M>
where M: Monoid,

Source

pub fn new(size: usize, f: impl Fn(usize) -> (usize, M::T)) -> Self

Source

pub fn double(&mut self)

Examples found in repository ?

crates/competitive/src/algorithm/doubling.rs (line 54)

37    pub fn kth(&mut self, mut pos: usize, mut k: usize) -> (usize, M::T) {
38        let mut x = M::unit();
39        for chunk in self.table.chunks_exact(self.size) {
40            if k & 1 == 1 {
41                let &(to, ref val) = &chunk[pos];
42                if to == !0 {
43                    return (!0, M::unit());
44                }
45                x = M::operate(&x, val);
46                pos = to;
47            }
48            k >>= 1;
49            if k == 0 {
50                break;
51            }
52        }
53        while k > 0 {
54            self.double();
55            if k & 1 == 1 {
56                let base = self.table.len() - self.size;
57                let &(to, ref val) = &self.table[base + pos];
58                if to == !0 {
59                    return (!0, M::unit());
60                }
61                x = M::operate(&x, val);
62                pos = to;
63            }
64            k >>= 1;
65        }
66        (pos, x)
67    }

Source

pub fn kth(&mut self, pos: usize, k: usize) -> (usize, M::T)

Source

pub fn kth_multiple( &self, queries: impl IntoIterator<Item = (usize, usize)>, ) -> Vec<(usize, M::T)>

queries: (pos, k) Return: (pos, acc)

Source

pub fn find_last( &self, pos: usize, pred: impl FnMut(usize, &M::T) -> bool, ) -> (usize, (usize, M::T))

Return: (k, (pos, acc))

Examples found in repository ?

crates/competitive/src/algorithm/doubling.rs (line 153)

148    pub fn find_first(
149        &self,
150        pos: usize,
151        mut pred: impl FnMut(usize, &M::T) -> bool,
152    ) -> Option<(usize, (usize, M::T))> {
153        let (mut k, (mut pos, mut x)) = self.find_last(pos, |k, x| !pred(k, x));
154        k += 1;
155        M::operate_assign(&mut x, &self.table[pos].1);
156        pos = self.table[pos].0;
157        if pred(pos, &x) {
158            Some((k, (pos, x)))
159        } else {
160            None
161        }
162    }