library_checker/data_structure/
majority_voting.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::FindMajorityOperation,
5    data_structure::{RangeFrequency, SegmentTree},
6};
7
8competitive::define_enum_scan! {
9    enum Query: usize {
10        0 => Update { p: usize, x: i32 }
11        1 => Query { l: usize, r: usize }
12    }
13}
14
15#[verify::library_checker("majority_voting")]
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}
library_checker/data_structure/majority_voting.rs

library_checker/data_structure/
majority_voting.rs
