contest_algorithms::range_query::sqrt_decomp

Trait MoState

Source 
pub trait MoState {
    type Q;
    type A;

    const L_R_RATIO: f64 = 1f64;

    // Required methods
    fn query(&self, q: &Self::Q) -> Self::A;
    fn insert_left(&mut self, pos: usize);
    fn remove_left(&mut self, pos: usize);

    // Provided methods
    fn insert_right(&mut self, pos: usize) { ... }
    fn remove_right(&mut self, pos: usize) { ... }
    fn process(&mut self, queries: &[(usize, usize, Self::Q)]) -> Vec<Self::A> { ... }
}
Expand description

A generic implementation of Mo’s algorithm, aka Query Sqrt Decomposition. It answers q offline queries over intervals in 0..n by shifting the query interval’s endpoints by one position at a time. Each endpoint incurs a total cost of at most n * sqrt(q * L_OP * R_OP).

Provided Associated Constants§

Source

const L_R_RATIO: f64 = 1f64

cost ratio L_OP / R_OP between a left endpoint and a right endpoint move

Required Associated Types§

Source

type Q

Source

type A

Required Methods§

Source

fn query(&self, q: &Self::Q) -> Self::A

Source

fn insert_left(&mut self, pos: usize)

Source

fn remove_left(&mut self, pos: usize)

Provided Methods§

Source

fn insert_right(&mut self, pos: usize)

Source

fn remove_right(&mut self, pos: usize)

Source

fn process(&mut self, queries: &[(usize, usize, Self::Q)]) -> Vec<Self::A>

After initializing self to a state corresponding to an empty interval, call this function to answer all your queries.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§