Struct RangeFrequencyProcessor 

struct RangeFrequencyProcessor {
    bit: BinaryIndexedTree<AdditiveOperation<i32>>,
    data: Vec<u64>,
}

Fields

bit: BinaryIndexedTree<AdditiveOperation<i32>>

data: Vec<u64>

Implementations

impl RangeFrequencyProcessor

fn new(size: usize) -> Self

Examples found in repository

crates/competitive/src/data_structure/range_frequency.rs (line 178)

    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
        for output_index in self.zero_queries {
            callback(output_index as usize, 0);
        }
        if let Some(mut queries) = self.static_queries.take() {
            let n = self.array.len();
            if queries.is_empty() {
                return;
            }
            let mut offsets = vec![0; n + 2];
            for &(left, right, _, _) in &queries {
                if left < right {
                    offsets[left as usize + 1] += 1;
                    offsets[right as usize + 1] += 1;
                }
            }
            for i in 0..=n {
                offsets[i + 1] += offsets[i];
            }
            let mut next = offsets.clone();
            let mut events = vec![0u32; 2 * queries.len()];
            for (i, &(left, right, _, output_index)) in queries.iter().enumerate() {
                if left >= right {
                    callback(output_index as usize, 0);
                    continue;
                }
                for (side, position) in [left, right].into_iter().enumerate() {
                    events[next[position as usize]] = (2 * i + side) as u32;
                    next[position as usize] += 1;
                }
            }
            let mut count = vec![0u32; self.values.len()];
            for position in 0..=n {
                for &endpoint in &events[offsets[position]..offsets[position + 1]] {
                    let query = (endpoint >> 1) as usize;
                    let frequency = count[queries[query].2 as usize];
                    if endpoint & 1 == 0 {
                        queries[query].0 = frequency;
                    } else {
                        callback(
                            queries[query].3 as usize,
                            (frequency - queries[query].0) as usize,
                        );
                    }
                }
                if position < n {
                    count[self.array[position] as usize] += 1;
                }
            }
            return;
        }
        let mut processor = RangeFrequencyProcessor::new(self.array.len());
        for (index, value) in self.array.into_iter().enumerate() {
            self.events.push((
                value,
                RangeFrequencyQuery::Remove {
                    index: index as u32,
                },
            ));
        }
        let mut offsets = vec![0; self.queried.len() + 1];
        for &(value, _) in &self.events {
            offsets[value as usize + 1] += self.queried[value as usize] as usize;
        }
        for i in 0..self.queried.len() {
            offsets[i + 1] += offsets[i];
        }
        let mut next = offsets.clone();
        let mut events = vec![RangeFrequencyQuery::Add { index: 0 }; *offsets.last().unwrap()];
        for (value, event) in self.events {
            let value = value as usize;
            if self.queried[value] != 0 {
                events[next[value]] = event;
                next[value] += 1;
            }
        }
        for range in offsets.windows(2) {
            for &query in &events[range[0]..range[1]] {
                match query {
                    RangeFrequencyQuery::Add { index } => {
                        processor.add(index);
                    }
                    RangeFrequencyQuery::Remove { index } => {
                        processor.remove(index);
                    }
                    RangeFrequencyQuery::Query {
                        left,
                        right,
                        output_index,
                    } => {
                        callback(output_index as usize, processor.query(left, right));
                    }
                }
            }
        }
    }

fn add(&mut self, index: u32)

Examples found in repository

crates/competitive/src/data_structure/range_frequency.rs (line 207)

    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
        for output_index in self.zero_queries {
            callback(output_index as usize, 0);
        }
        if let Some(mut queries) = self.static_queries.take() {
            let n = self.array.len();
            if queries.is_empty() {
                return;
            }
            let mut offsets = vec![0; n + 2];
            for &(left, right, _, _) in &queries {
                if left < right {
                    offsets[left as usize + 1] += 1;
                    offsets[right as usize + 1] += 1;
                }
            }
            for i in 0..=n {
                offsets[i + 1] += offsets[i];
            }
            let mut next = offsets.clone();
            let mut events = vec![0u32; 2 * queries.len()];
            for (i, &(left, right, _, output_index)) in queries.iter().enumerate() {
                if left >= right {
                    callback(output_index as usize, 0);
                    continue;
                }
                for (side, position) in [left, right].into_iter().enumerate() {
                    events[next[position as usize]] = (2 * i + side) as u32;
                    next[position as usize] += 1;
                }
            }
            let mut count = vec![0u32; self.values.len()];
            for position in 0..=n {
                for &endpoint in &events[offsets[position]..offsets[position + 1]] {
                    let query = (endpoint >> 1) as usize;
                    let frequency = count[queries[query].2 as usize];
                    if endpoint & 1 == 0 {
                        queries[query].0 = frequency;
                    } else {
                        callback(
                            queries[query].3 as usize,
                            (frequency - queries[query].0) as usize,
                        );
                    }
                }
                if position < n {
                    count[self.array[position] as usize] += 1;
                }
            }
            return;
        }
        let mut processor = RangeFrequencyProcessor::new(self.array.len());
        for (index, value) in self.array.into_iter().enumerate() {
            self.events.push((
                value,
                RangeFrequencyQuery::Remove {
                    index: index as u32,
                },
            ));
        }
        let mut offsets = vec![0; self.queried.len() + 1];
        for &(value, _) in &self.events {
            offsets[value as usize + 1] += self.queried[value as usize] as usize;
        }
        for i in 0..self.queried.len() {
            offsets[i + 1] += offsets[i];
        }
        let mut next = offsets.clone();
        let mut events = vec![RangeFrequencyQuery::Add { index: 0 }; *offsets.last().unwrap()];
        for (value, event) in self.events {
            let value = value as usize;
            if self.queried[value] != 0 {
                events[next[value]] = event;
                next[value] += 1;
            }
        }
        for range in offsets.windows(2) {
            for &query in &events[range[0]..range[1]] {
                match query {
                    RangeFrequencyQuery::Add { index } => {
                        processor.add(index);
                    }
                    RangeFrequencyQuery::Remove { index } => {
                        processor.remove(index);
                    }
                    RangeFrequencyQuery::Query {
                        left,
                        right,
                        output_index,
                    } => {
                        callback(output_index as usize, processor.query(left, right));
                    }
                }
            }
        }
    }

fn remove(&mut self, index: u32)

Examples found in repository

crates/competitive/src/data_structure/range_frequency.rs (line 210)

    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
        for output_index in self.zero_queries {
            callback(output_index as usize, 0);
        }
        if let Some(mut queries) = self.static_queries.take() {
            let n = self.array.len();
            if queries.is_empty() {
                return;
            }
            let mut offsets = vec![0; n + 2];
            for &(left, right, _, _) in &queries {
                if left < right {
                    offsets[left as usize + 1] += 1;
                    offsets[right as usize + 1] += 1;
                }
            }
            for i in 0..=n {
                offsets[i + 1] += offsets[i];
            }
            let mut next = offsets.clone();
            let mut events = vec![0u32; 2 * queries.len()];
            for (i, &(left, right, _, output_index)) in queries.iter().enumerate() {
                if left >= right {
                    callback(output_index as usize, 0);
                    continue;
                }
                for (side, position) in [left, right].into_iter().enumerate() {
                    events[next[position as usize]] = (2 * i + side) as u32;
                    next[position as usize] += 1;
                }
            }
            let mut count = vec![0u32; self.values.len()];
            for position in 0..=n {
                for &endpoint in &events[offsets[position]..offsets[position + 1]] {
                    let query = (endpoint >> 1) as usize;
                    let frequency = count[queries[query].2 as usize];
                    if endpoint & 1 == 0 {
                        queries[query].0 = frequency;
                    } else {
                        callback(
                            queries[query].3 as usize,
                            (frequency - queries[query].0) as usize,
                        );
                    }
                }
                if position < n {
                    count[self.array[position] as usize] += 1;
                }
            }
            return;
        }
        let mut processor = RangeFrequencyProcessor::new(self.array.len());
        for (index, value) in self.array.into_iter().enumerate() {
            self.events.push((
                value,
                RangeFrequencyQuery::Remove {
                    index: index as u32,
                },
            ));
        }
        let mut offsets = vec![0; self.queried.len() + 1];
        for &(value, _) in &self.events {
            offsets[value as usize + 1] += self.queried[value as usize] as usize;
        }
        for i in 0..self.queried.len() {
            offsets[i + 1] += offsets[i];
        }
        let mut next = offsets.clone();
        let mut events = vec![RangeFrequencyQuery::Add { index: 0 }; *offsets.last().unwrap()];
        for (value, event) in self.events {
            let value = value as usize;
            if self.queried[value] != 0 {
                events[next[value]] = event;
                next[value] += 1;
            }
        }
        for range in offsets.windows(2) {
            for &query in &events[range[0]..range[1]] {
                match query {
                    RangeFrequencyQuery::Add { index } => {
                        processor.add(index);
                    }
                    RangeFrequencyQuery::Remove { index } => {
                        processor.remove(index);
                    }
                    RangeFrequencyQuery::Query {
                        left,
                        right,
                        output_index,
                    } => {
                        callback(output_index as usize, processor.query(left, right));
                    }
                }
            }
        }
    }

fn query(&self, left: u32, right: u32) -> usize

Examples found in repository

crates/competitive/src/data_structure/range_frequency.rs (line 217)

    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
        for output_index in self.zero_queries {
            callback(output_index as usize, 0);
        }
        if let Some(mut queries) = self.static_queries.take() {
            let n = self.array.len();
            if queries.is_empty() {
                return;
            }
            let mut offsets = vec![0; n + 2];
            for &(left, right, _, _) in &queries {
                if left < right {
                    offsets[left as usize + 1] += 1;
                    offsets[right as usize + 1] += 1;
                }
            }
            for i in 0..=n {
                offsets[i + 1] += offsets[i];
            }
            let mut next = offsets.clone();
            let mut events = vec![0u32; 2 * queries.len()];
            for (i, &(left, right, _, output_index)) in queries.iter().enumerate() {
                if left >= right {
                    callback(output_index as usize, 0);
                    continue;
                }
                for (side, position) in [left, right].into_iter().enumerate() {
                    events[next[position as usize]] = (2 * i + side) as u32;
                    next[position as usize] += 1;
                }
            }
            let mut count = vec![0u32; self.values.len()];
            for position in 0..=n {
                for &endpoint in &events[offsets[position]..offsets[position + 1]] {
                    let query = (endpoint >> 1) as usize;
                    let frequency = count[queries[query].2 as usize];
                    if endpoint & 1 == 0 {
                        queries[query].0 = frequency;
                    } else {
                        callback(
                            queries[query].3 as usize,
                            (frequency - queries[query].0) as usize,
                        );
                    }
                }
                if position < n {
                    count[self.array[position] as usize] += 1;
                }
            }
            return;
        }
        let mut processor = RangeFrequencyProcessor::new(self.array.len());
        for (index, value) in self.array.into_iter().enumerate() {
            self.events.push((
                value,
                RangeFrequencyQuery::Remove {
                    index: index as u32,
                },
            ));
        }
        let mut offsets = vec![0; self.queried.len() + 1];
        for &(value, _) in &self.events {
            offsets[value as usize + 1] += self.queried[value as usize] as usize;
        }
        for i in 0..self.queried.len() {
            offsets[i + 1] += offsets[i];
        }
        let mut next = offsets.clone();
        let mut events = vec![RangeFrequencyQuery::Add { index: 0 }; *offsets.last().unwrap()];
        for (value, event) in self.events {
            let value = value as usize;
            if self.queried[value] != 0 {
                events[next[value]] = event;
                next[value] += 1;
            }
        }
        for range in offsets.windows(2) {
            for &query in &events[range[0]..range[1]] {
                match query {
                    RangeFrequencyQuery::Add { index } => {
                        processor.add(index);
                    }
                    RangeFrequencyQuery::Remove { index } => {
                        processor.remove(index);
                    }
                    RangeFrequencyQuery::Query {
                        left,
                        right,
                        output_index,
                    } => {
                        callback(output_index as usize, processor.query(left, right));
                    }
                }
            }
        }
    }

Trait Implementations

impl Clone for RangeFrequencyProcessor

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for RangeFrequencyProcessor

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

Formats the value using the given formatter.