Second Largest Query の解説

1こめと2こめをもっておくセグ木で殴る。

#[derive(Debug, Clone, Copy)]
struct M {
    first: (usize, usize),
    second: (usize, usize),
}

impl Monoid for M {
    type S = M;
    fn identity() -> Self::S {
        M {
            first: (0, 0),
            second: (0, 0),
        }
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        let mut v = vec![a.first, a.second, b.first, b.second];
        v.sort_by_key(|&e| Reverse(e.0));
        let mut vv = vec![];
        for &(num, count) in v.iter() {
            if vv.is_empty() {
                vv.push((num, count));
                continue;
            }
            let &(lanum, lacount) = vv.last().unwrap();
            if lanum == num {
                vv.pop().unwrap();
                vv.push((num, count + lacount));
            } else {
                vv.push((num, count));
            }

        }
        let f = vv[0];
        let &s = vv.get(1).unwrap_or(&(0, 0));
        M {
            first: f,
            second: s,
        }
    }
}

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
    }
    let mut seg = Segtree::<M>::new(n);
    for i in 0..n {
        seg.set(
            i,
            M {
                first: (a[i], 1),
                second: (0, 0),
            },
        );
    }
    for _ in 0..q {
        input! {
            o: usize
        }
        if o == 1 {
            input! {
                p: Usize1,
                x: usize
            }
            seg.set(p, M {first: (x, 1), second: (0, 0)});
        } else {
            input! {
                l: Usize1,
                r: Usize1
            }
            let ans = seg.prod(l..=r).second;
            println!("{}", ans.1);
        }
    }
}