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

6pub fn point_set_range_frequency(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, a: [i32; n]);
10    let mut rf = RangeFrequency::new(a);
11    for _ in 0..q {
12        scan!(scanner, ty);
13        if ty == 0 {
14            scan!(scanner, k, v: i32);
15            rf.set(k, v);
16        } else {
17            scan!(scanner, l, r, x: i32);
18            rf.query(l, r, x);
19        }
20    }
21    let results = rf.execute();
22    iter_print!(writer, @lf @it results);
23}

More examples

Hide additional examples

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

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

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

6pub fn point_set_range_frequency(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, a: [i32; n]);
10    let mut rf = RangeFrequency::new(a);
11    for _ in 0..q {
12        scan!(scanner, ty);
13        if ty == 0 {
14            scan!(scanner, k, v: i32);
15            rf.set(k, v);
16        } else {
17            scan!(scanner, l, r, x: i32);
18            rf.query(l, r, x);
19        }
20    }
21    let results = rf.execute();
22    iter_print!(writer, @lf @it results);
23}

More examples

Hide additional examples

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

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

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

6pub fn point_set_range_frequency(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, a: [i32; n]);
10    let mut rf = RangeFrequency::new(a);
11    for _ in 0..q {
12        scan!(scanner, ty);
13        if ty == 0 {
14            scan!(scanner, k, v: i32);
15            rf.set(k, v);
16        } else {
17            scan!(scanner, l, r, x: i32);
18            rf.query(l, r, x);
19        }
20    }
21    let results = rf.execute();
22    iter_print!(writer, @lf @it results);
23}

More examples

Hide additional examples

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

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

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 31-35)

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

Source

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

Examples found in repository ?

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

6pub fn point_set_range_frequency(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q, a: [i32; n]);
10    let mut rf = RangeFrequency::new(a);
11    for _ in 0..q {
12        scan!(scanner, ty);
13        if ty == 0 {
14            scan!(scanner, k, v: i32);
15            rf.set(k, v);
16        } else {
17            scan!(scanner, l, r, x: i32);
18            rf.query(l, r, x);
19        }
20    }
21    let results = rf.execute();
22    iter_print!(writer, @lf @it results);
23}