Struct RangeFrequency

Source

pub struct RangeFrequency<T>where
    T: Clone + Eq + Hash,{
    array: Vec<u32>,
    values: FibHashMap<T, u32>,
    events: Vec<(u32, RangeFrequencyQuery)>,
    queried: Vec<u8>,
    static_queries: Option<Vec<(u32, u32, u32, u32)>>,
    zero_queries: Vec<u32>,
    output_size: usize,
}

Fields§

§array: Vec<u32>§values: FibHashMap<T, u32>§events: Vec<(u32, RangeFrequencyQuery)>§queried: Vec<u8>§static_queries: Option<Vec<(u32, u32, u32, u32)>>§zero_queries: Vec<u32>§output_size: usize

Implementations§

Source §

impl<T> RangeFrequency<T>
where T: Clone + Eq + Hash,

Source

pub fn new(array: Vec<T>) -> Self

Examples found in repository ?

crates/library_checker/src/data_structure/static_range_frequency.rs (line 8)

5pub fn static_range_frequency(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, q, a: [u32; n]);
8    let mut range_frequency = RangeFrequency::new(a);
9    for _ in 0..q {
10        sc!(l, r, x: u32);
11        range_frequency.query(l, r, x);
12    }
13    pp!(@lf @it range_frequency.execute());
14}

More examples

Hide additional examples

crates/library_checker/src/data_structure/point_set_range_frequency.rs (line 15)

12pub fn point_set_range_frequency(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q, a: [i32; n]);
15    let mut rf = RangeFrequency::new(a);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Set { k, v } => {
20                rf.set(k, v);
21            }
22            Query::Query { l, r, x } => {
23                rf.query(l, r, x);
24            }
25        }
26    }
27    let results = rf.execute();
28    pp!(@lf @it results);
29}

crates/library_checker/src/data_structure/majority_voting.rs (line 21)

15pub fn majority_voting(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [i32; n]);
18    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
19        a.iter().map(|&a| (Some(a), 1)).collect(),
20    );
21    let mut rf = RangeFrequency::new(a);
22    let mut out = vec![];
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Update { p, x } => {
27                seg.set(p, (Some(x), 1));
28                rf.set(p, x);
29            }
30            Query::Query { l, r } => {
31                let x = seg.fold(l..r).0.unwrap_or(-1);
32                out.push((x, r - l));
33                rf.query(l, r, x);
34            }
35        }
36    }
37    rf.execute_with_callback(|i, v| {
38        if out[i].1 >= 2 * v {
39            out[i].0 = -1;
40        }
41    });
42    pp!(@lf @it out.iter().map(|&(x, _)| x));
43}

Source

fn value_id(&mut self, value: T) -> u32

Examples found in repository ?

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

37    pub fn new(array: Vec<T>) -> Self {
38        let mut result = Self {
39            array: Vec::with_capacity(array.len()),
40            values: FibHashMap::with_capacity_and_hasher(array.len(), Default::default()),
41            events: Vec::new(),
42            queried: Vec::new(),
43            static_queries: Some(Vec::new()),
44            zero_queries: Vec::new(),
45            output_size: 0,
46        };
47        for value in array {
48            let value = result.value_id(value);
49            result.array.push(value);
50        }
51        result
52    }
53
54    fn value_id(&mut self, value: T) -> u32 {
55        match self.values.entry(value) {
56            Entry::Occupied(entry) => *entry.get(),
57            Entry::Vacant(entry) => {
58                let id = self.queried.len() as u32;
59                entry.insert(id);
60                self.queried.push(0);
61                id
62            }
63        }
64    }
65
66    pub fn set(&mut self, index: usize, value: T) {
67        if let Some(queries) = self.static_queries.take() {
68            self.events.reserve(self.array.len() + queries.len() + 2);
69            for (index, &value) in self.array.iter().enumerate() {
70                self.events.push((
71                    value,
72                    RangeFrequencyQuery::Add {
73                        index: index as u32,
74                    },
75                ));
76            }
77            for (left, right, value, output_index) in queries {
78                self.events.push((
79                    value,
80                    RangeFrequencyQuery::Query {
81                        left,
82                        right,
83                        output_index,
84                    },
85                ));
86            }
87        }
88        let value = self.value_id(value);
89        let old_value = replace(&mut self.array[index], value);
90        self.events.push((
91            old_value,
92            RangeFrequencyQuery::Remove {
93                index: index as u32,
94            },
95        ));
96        self.events.push((
97            value,
98            RangeFrequencyQuery::Add {
99                index: index as u32,
100            },
101        ));
102    }

Source

pub fn set(&mut self, index: usize, value: T)

Examples found in repository ?

crates/library_checker/src/data_structure/point_set_range_frequency.rs (line 20)

12pub fn point_set_range_frequency(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q, a: [i32; n]);
15    let mut rf = RangeFrequency::new(a);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Set { k, v } => {
20                rf.set(k, v);
21            }
22            Query::Query { l, r, x } => {
23                rf.query(l, r, x);
24            }
25        }
26    }
27    let results = rf.execute();
28    pp!(@lf @it results);
29}

More examples

Hide additional examples

crates/library_checker/src/data_structure/majority_voting.rs (line 28)

15pub fn majority_voting(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [i32; n]);
18    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
19        a.iter().map(|&a| (Some(a), 1)).collect(),
20    );
21    let mut rf = RangeFrequency::new(a);
22    let mut out = vec![];
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Update { p, x } => {
27                seg.set(p, (Some(x), 1));
28                rf.set(p, x);
29            }
30            Query::Query { l, r } => {
31                let x = seg.fold(l..r).0.unwrap_or(-1);
32                out.push((x, r - l));
33                rf.query(l, r, x);
34            }
35        }
36    }
37    rf.execute_with_callback(|i, v| {
38        if out[i].1 >= 2 * v {
39            out[i].0 = -1;
40        }
41    });
42    pp!(@lf @it out.iter().map(|&(x, _)| x));
43}

Source

pub fn query(&mut self, left: usize, right: usize, value: T) -> usize

Examples found in repository ?

crates/library_checker/src/data_structure/static_range_frequency.rs (line 11)

5pub fn static_range_frequency(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, q, a: [u32; n]);
8    let mut range_frequency = RangeFrequency::new(a);
9    for _ in 0..q {
10        sc!(l, r, x: u32);
11        range_frequency.query(l, r, x);
12    }
13    pp!(@lf @it range_frequency.execute());
14}

More examples

Hide additional examples

crates/library_checker/src/data_structure/point_set_range_frequency.rs (line 23)

12pub fn point_set_range_frequency(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q, a: [i32; n]);
15    let mut rf = RangeFrequency::new(a);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Set { k, v } => {
20                rf.set(k, v);
21            }
22            Query::Query { l, r, x } => {
23                rf.query(l, r, x);
24            }
25        }
26    }
27    let results = rf.execute();
28    pp!(@lf @it results);
29}

crates/library_checker/src/data_structure/majority_voting.rs (line 33)

15pub fn majority_voting(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [i32; n]);
18    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
19        a.iter().map(|&a| (Some(a), 1)).collect(),
20    );
21    let mut rf = RangeFrequency::new(a);
22    let mut out = vec![];
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Update { p, x } => {
27                seg.set(p, (Some(x), 1));
28                rf.set(p, x);
29            }
30            Query::Query { l, r } => {
31                let x = seg.fold(l..r).0.unwrap_or(-1);
32                out.push((x, r - l));
33                rf.query(l, r, x);
34            }
35        }
36    }
37    rf.execute_with_callback(|i, v| {
38        if out[i].1 >= 2 * v {
39            out[i].0 = -1;
40        }
41    });
42    pp!(@lf @it out.iter().map(|&(x, _)| x));
43}

Source

pub fn execute_with_callback(self, callback: impl FnMut(usize, usize))

Examples found in repository ?

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

224    pub fn execute(self) -> Vec<usize> {
225        let mut results = vec![0; self.output_size];
226        self.execute_with_callback(|i, v| results[i] = v);
227        results
228    }

More examples

Hide additional examples

crates/library_checker/src/data_structure/majority_voting.rs (lines 37-41)

15pub fn majority_voting(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [i32; n]);
18    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
19        a.iter().map(|&a| (Some(a), 1)).collect(),
20    );
21    let mut rf = RangeFrequency::new(a);
22    let mut out = vec![];
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Update { p, x } => {
27                seg.set(p, (Some(x), 1));
28                rf.set(p, x);
29            }
30            Query::Query { l, r } => {
31                let x = seg.fold(l..r).0.unwrap_or(-1);
32                out.push((x, r - l));
33                rf.query(l, r, x);
34            }
35        }
36    }
37    rf.execute_with_callback(|i, v| {
38        if out[i].1 >= 2 * v {
39            out[i].0 = -1;
40        }
41    });
42    pp!(@lf @it out.iter().map(|&(x, _)| x));
43}

Source

pub fn execute(self) -> Vec<usize>

Examples found in repository ?

crates/library_checker/src/data_structure/static_range_frequency.rs (line 13)

5pub fn static_range_frequency(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, q, a: [u32; n]);
8    let mut range_frequency = RangeFrequency::new(a);
9    for _ in 0..q {
10        sc!(l, r, x: u32);
11        range_frequency.query(l, r, x);
12    }
13    pp!(@lf @it range_frequency.execute());
14}

More examples

Hide additional examples

crates/library_checker/src/data_structure/point_set_range_frequency.rs (line 27)

12pub fn point_set_range_frequency(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q, a: [i32; n]);
15    let mut rf = RangeFrequency::new(a);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Set { k, v } => {
20                rf.set(k, v);
21            }
22            Query::Query { l, r, x } => {
23                rf.query(l, r, x);
24            }
25        }
26    }
27    let results = rf.execute();
28    pp!(@lf @it results);
29}