competitive::data_structure::range_frequency

Struct RangeFrequencyProcessor

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

Fields§

§bit: BinaryIndexedTree<AdditiveOperation<i32>>§data: Vec<u64>

Implementations§

Source §

impl RangeFrequencyProcessor

Source

fn new(size: usize) -> Self

Examples found in repository ?

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

74    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
75        let mut processor = RangeFrequencyProcessor::new(self.array.len());
76        for (index, value) in self.array.into_iter().enumerate() {
77            self.queries
78                .entry(value)
79                .or_default()
80                .push(RangeFrequencyQuery::Remove { index });
81        }
82        for (_, queries) in self.queries {
83            for query in queries {
84                match query {
85                    RangeFrequencyQuery::Add { index } => {
86                        processor.add(index);
87                    }
88                    RangeFrequencyQuery::Remove { index } => {
89                        processor.remove(index);
90                    }
91                    RangeFrequencyQuery::Query {
92                        left,
93                        right,
94                        output_index,
95                    } => {
96                        callback(output_index, processor.query(left, right));
97                    }
98                }
99            }
100        }
101    }

Source

fn add(&mut self, index: usize)

Examples found in repository ?

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

74    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
75        let mut processor = RangeFrequencyProcessor::new(self.array.len());
76        for (index, value) in self.array.into_iter().enumerate() {
77            self.queries
78                .entry(value)
79                .or_default()
80                .push(RangeFrequencyQuery::Remove { index });
81        }
82        for (_, queries) in self.queries {
83            for query in queries {
84                match query {
85                    RangeFrequencyQuery::Add { index } => {
86                        processor.add(index);
87                    }
88                    RangeFrequencyQuery::Remove { index } => {
89                        processor.remove(index);
90                    }
91                    RangeFrequencyQuery::Query {
92                        left,
93                        right,
94                        output_index,
95                    } => {
96                        callback(output_index, processor.query(left, right));
97                    }
98                }
99            }
100        }
101    }

Source

fn remove(&mut self, index: usize)

Examples found in repository ?

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

74    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
75        let mut processor = RangeFrequencyProcessor::new(self.array.len());
76        for (index, value) in self.array.into_iter().enumerate() {
77            self.queries
78                .entry(value)
79                .or_default()
80                .push(RangeFrequencyQuery::Remove { index });
81        }
82        for (_, queries) in self.queries {
83            for query in queries {
84                match query {
85                    RangeFrequencyQuery::Add { index } => {
86                        processor.add(index);
87                    }
88                    RangeFrequencyQuery::Remove { index } => {
89                        processor.remove(index);
90                    }
91                    RangeFrequencyQuery::Query {
92                        left,
93                        right,
94                        output_index,
95                    } => {
96                        callback(output_index, processor.query(left, right));
97                    }
98                }
99            }
100        }
101    }

Source

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

Examples found in repository ?

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

74    pub fn execute_with_callback(mut self, mut callback: impl FnMut(usize, usize)) {
75        let mut processor = RangeFrequencyProcessor::new(self.array.len());
76        for (index, value) in self.array.into_iter().enumerate() {
77            self.queries
78                .entry(value)
79                .or_default()
80                .push(RangeFrequencyQuery::Remove { index });
81        }
82        for (_, queries) in self.queries {
83            for query in queries {
84                match query {
85                    RangeFrequencyQuery::Add { index } => {
86                        processor.add(index);
87                    }
88                    RangeFrequencyQuery::Remove { index } => {
89                        processor.remove(index);
90                    }
91                    RangeFrequencyQuery::Query {
92                        left,
93                        right,
94                        output_index,
95                    } => {
96                        callback(output_index, processor.query(left, right));
97                    }
98                }
99            }
100        }
101    }