Struct RangeFrequency

Source

pub struct RangeFrequency<T>where
    T: Clone + Eq + Hash,{
    array: Vec<T>,
    queries: HashMap<T, Vec<RangeFrequencyQuery>>,
    output_size: usize,
}

Fields§

§array: Vec<T>§queries: HashMap<T, Vec<RangeFrequencyQuery>>§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/point_set_range_frequency.rs (line 17)

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

More examples

Hide additional examples

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

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

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

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

More examples

Hide additional examples

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

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

Source

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

Examples found in repository ?

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

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

More examples

Hide additional examples

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

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

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

103    pub fn execute(self) -> Vec<usize> {
104        let mut results = vec![0; self.output_size];
105        self.execute_with_callback(|i, v| results[i] = v);
106        results
107    }

More examples

Hide additional examples

crates/library_checker/src/data_structure/majority_voting.rs (lines 39-43)

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

Source

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

Examples found in repository ?

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

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