Trait contest_algorithms::range_query::sqrt_decomp::MoState

pub trait MoState {
    type Q;
    type A;

    const L_R_RATIO: f64;

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

    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> { ... }
}

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).

Associated Types

type Q

type A

Loading content...

Associated Constants

const L_R_RATIO: f64

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

Loading content...

Required methods

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

fn insert_left(&mut self, pos: usize)

fn remove_left(&mut self, pos: usize)

Loading content...

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>

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

Loading content...

Implementors

impl MoState for DistinctVals

type Q = ()

type A = usize

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

fn insert_left(&mut self, pos: usize)

fn remove_left(&mut self, pos: usize)

Loading content...