library_checker/data_structure/
majority_voting.rs

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

library_checker/data_structure/majority_voting.rs

library_checker/data_structure/
majority_voting.rs