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
8#[verify::library_checker("majority_voting")]
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}

library_checker/data_structure/majority_voting.rs

library_checker/data_structure/
majority_voting.rs