Struct FunctionalGraphDoubling

Source

pub struct FunctionalGraphDoubling<M>where
    M: Group,{
    depth_to_cycle: Vec<usize>,
    cycle_entry: Vec<usize>,
    cycle_id: Vec<usize>,
    cycle_pos: Vec<usize>,
    cycles: Vec<Vec<usize>>,
    cycle_prefix: Vec<Vec<M::T>>,
    prefix_up: Vec<M::T>,
    la: LevelAncestor,
}

Fields§

§depth_to_cycle: Vec<usize>§cycle_entry: Vec<usize>§cycle_id: Vec<usize>§cycle_pos: Vec<usize>§cycles: Vec<Vec<usize>>§cycle_prefix: Vec<Vec<M::T>>§prefix_up: Vec<M::T>§la: LevelAncestor

Implementations§

Source §

impl<M> FunctionalGraphDoubling<M>
where M: Group,

Source

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

Source

fn acc_to_ancestor(&self, u: usize, ancestor: usize) -> M::T

Examples found in repository ?

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

335    pub fn kth(&self, u: usize, k: usize) -> (usize, M::T) {
336        let depth = self.depth_to_cycle[u];
337        if k <= depth {
338            let ancestor = self.la.la(u, k).unwrap();
339            let acc = self.acc_to_ancestor(u, ancestor);
340            return (ancestor, acc);
341        }
342        let entry = self.cycle_entry[u];
343        let acc_tree = self.acc_to_ancestor(u, entry);
344        let steps = k - depth;
345        let pos = self.cycle_jump_from(entry, steps);
346        let acc_cycle = self.cycle_acc_from(entry, steps);
347        let acc = M::operate(&acc_tree, &acc_cycle);
348        (pos, acc)
349    }

Source

fn cycle_segment(&self, cycle_id: usize, start: usize, len: usize) -> M::T

Examples found in repository ?

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

306    fn cycle_acc_from(&self, entry: usize, steps: usize) -> M::T {
307        if steps == 0 {
308            return M::unit();
309        }
310        let cycle_id = self.cycle_id[entry];
311        let start = self.cycle_pos[entry];
312        let len = self.cycles[cycle_id].len();
313        let q = steps / len;
314        let r = steps % len;
315        let rem = self.cycle_segment(cycle_id, start, r);
316        if q == 0 {
317            return rem;
318        }
319        let full = self.cycle_segment(cycle_id, start, len);
320        let pow = M::pow(full, q);
321        M::operate(&pow, &rem)
322    }

Source

fn cycle_acc_from(&self, entry: usize, steps: usize) -> M::T

Examples found in repository ?

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

335    pub fn kth(&self, u: usize, k: usize) -> (usize, M::T) {
336        let depth = self.depth_to_cycle[u];
337        if k <= depth {
338            let ancestor = self.la.la(u, k).unwrap();
339            let acc = self.acc_to_ancestor(u, ancestor);
340            return (ancestor, acc);
341        }
342        let entry = self.cycle_entry[u];
343        let acc_tree = self.acc_to_ancestor(u, entry);
344        let steps = k - depth;
345        let pos = self.cycle_jump_from(entry, steps);
346        let acc_cycle = self.cycle_acc_from(entry, steps);
347        let acc = M::operate(&acc_tree, &acc_cycle);
348        (pos, acc)
349    }

Source

fn cycle_jump_from(&self, entry: usize, steps: usize) -> usize

Examples found in repository ?

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

335    pub fn kth(&self, u: usize, k: usize) -> (usize, M::T) {
336        let depth = self.depth_to_cycle[u];
337        if k <= depth {
338            let ancestor = self.la.la(u, k).unwrap();
339            let acc = self.acc_to_ancestor(u, ancestor);
340            return (ancestor, acc);
341        }
342        let entry = self.cycle_entry[u];
343        let acc_tree = self.acc_to_ancestor(u, entry);
344        let steps = k - depth;
345        let pos = self.cycle_jump_from(entry, steps);
346        let acc_cycle = self.cycle_acc_from(entry, steps);
347        let acc = M::operate(&acc_tree, &acc_cycle);
348        (pos, acc)
349    }

Source

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

Examples found in repository ?

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

353    pub fn kth_multiple(
354        &self,
355        queries: impl IntoIterator<Item = (usize, usize)>,
356    ) -> Vec<(usize, M::T)> {
357        queries.into_iter().map(|(u, k)| self.kth(u, k)).collect()
358    }