Struct SubmaskRangeQuery 

pub struct SubmaskRangeQuery { /* private fields */ }

Implementations

impl SubmaskRangeQuery

pub fn new(bit_width: u32) -> Self

pub fn new_with_queries( queries: impl IntoIterator<Item = (QueryKind, u32)> + ExactSizeIterator + Clone, ) -> Self

Examples found in repository

crates/competitive/src/data_structure/submask_range_query.rs (lines 154-157)

    pub fn solve(self) -> Vec<G::T> {
        let s = SubmaskRangeQuery::new_with_queries(self.query.iter().map(|q| match q {
            Query::Get { m } => (QueryKind::Get, *m),
            Query::Update { m, .. } => (QueryKind::Update, *m),
        }));
        let out_size = self
            .query
            .iter()
            .filter(|q| matches!(q, Query::Get { .. }))
            .count();
        let mut out = Vec::with_capacity(out_size);
        let mut data = vec![G::unit(); 1 << s.bit_width];
        for q in self.query {
            match q {
                Query::Get { m } => {
                    let mut f = G::unit();
                    let mut g = G::unit();
                    for (k, inv) in s.get_query(m) {
                        if inv {
                            G::operate_assign(&mut g, &data[k as usize]);
                        } else {
                            G::operate_assign(&mut f, &data[k as usize]);
                        }
                    }
                    out.push(G::rinv_operate(&f, &g));
                }
                Query::Update { m, x } => {
                    for k in s.update_query(m) {
                        G::operate_assign(&mut data[k as usize], &x);
                    }
                }
            }
        }
        out
    }

pub fn builder<G>() -> SubmaskRangeQueryBuilder<G>

where G: Group,

pub fn get_query(&self, m: u32) -> impl Iterator<Item = (u32, bool)>

Examples found in repository

crates/competitive/src/data_structure/submask_range_query.rs (line 170)

    pub fn solve(self) -> Vec<G::T> {
        let s = SubmaskRangeQuery::new_with_queries(self.query.iter().map(|q| match q {
            Query::Get { m } => (QueryKind::Get, *m),
            Query::Update { m, .. } => (QueryKind::Update, *m),
        }));
        let out_size = self
            .query
            .iter()
            .filter(|q| matches!(q, Query::Get { .. }))
            .count();
        let mut out = Vec::with_capacity(out_size);
        let mut data = vec![G::unit(); 1 << s.bit_width];
        for q in self.query {
            match q {
                Query::Get { m } => {
                    let mut f = G::unit();
                    let mut g = G::unit();
                    for (k, inv) in s.get_query(m) {
                        if inv {
                            G::operate_assign(&mut g, &data[k as usize]);
                        } else {
                            G::operate_assign(&mut f, &data[k as usize]);
                        }
                    }
                    out.push(G::rinv_operate(&f, &g));
                }
                Query::Update { m, x } => {
                    for k in s.update_query(m) {
                        G::operate_assign(&mut data[k as usize], &x);
                    }
                }
            }
        }
        out
    }

pub fn update_query(&self, m: u32) -> impl Iterator<Item = u32>

Examples found in repository

crates/competitive/src/data_structure/submask_range_query.rs (line 180)

    pub fn solve(self) -> Vec<G::T> {
        let s = SubmaskRangeQuery::new_with_queries(self.query.iter().map(|q| match q {
            Query::Get { m } => (QueryKind::Get, *m),
            Query::Update { m, .. } => (QueryKind::Update, *m),
        }));
        let out_size = self
            .query
            .iter()
            .filter(|q| matches!(q, Query::Get { .. }))
            .count();
        let mut out = Vec::with_capacity(out_size);
        let mut data = vec![G::unit(); 1 << s.bit_width];
        for q in self.query {
            match q {
                Query::Get { m } => {
                    let mut f = G::unit();
                    let mut g = G::unit();
                    for (k, inv) in s.get_query(m) {
                        if inv {
                            G::operate_assign(&mut g, &data[k as usize]);
                        } else {
                            G::operate_assign(&mut f, &data[k as usize]);
                        }
                    }
                    out.push(G::rinv_operate(&f, &g));
                }
                Query::Update { m, x } => {
                    for k in s.update_query(m) {
                        G::operate_assign(&mut data[k as usize], &x);
                    }
                }
            }
        }
        out
    }

Trait Implementations

impl Clone for SubmaskRangeQuery

fn clone(&self) -> SubmaskRangeQuery

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SubmaskRangeQuery

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Copy for SubmaskRangeQuery