AtCoder Beginner Contest 343 F

https://atcoder.jp/contests/abc343/tasks/abc343_f

木を作って、各ノードに大きい方から2番目までの値と個数を保持しておけばよいです。
Boxを外すときas_ref()を使いますが、変更するならas_mut()を使うんですね。

// Second Largest Query
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Top2 ////////////////////

#[derive(Clone, Copy)]
struct Top2 {
    one: (i32, usize),
    two: (i32, usize)
}

impl Top2 {
    fn union(&self, other: &Top2) -> Top2 {
        if self.one.0 == other.one.0 {
            let one = (self.one.0, self.one.1 + other.one.1);
            let two = Top2::add(self.two, other.two);
            Top2 { one, two }
        }
        else if self.one.0 > other.one.0 {
            let one = self.one;
            let two = Top2::add(self.two, other.one);
            Top2 { one, two }
        }
        else {
            let one = other.one;
            let two = Top2::add(self.one, other.two);
            Top2 { one, two }
        }
    }
    
    fn add(a: (i32, usize), b: (i32, usize)) -> (i32, usize) {
        if a.0 == b.0 {
            (a.0, a.1 + b.1)
        }
        else if a.0 > b.0 {
            a
        }
        else {
            b
        }
    }
}


//////////////////// Node ////////////////////

struct Node {
    first: usize,
    last: usize,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
    top2: Top2,
}

impl Node {
    fn new(first: usize, last: usize, A: &Vec<i32>) -> Self {
        let mid = (first + last) / 2;
        if last - first == 1 {
            let top2 = Top2 { one: (A[first], 1), two: (0, 0) };
            Node { first, last, left: None, right: None, top2 }
        }
        else {
            let left = Box::new(Node::new(first, mid, A));
            let right = Box::new(Node::new(mid, last, A));
            let top2 = left.top2.union(&right.top2);
            Node { first, last, left: Some(left), right: Some(right), top2 }
        }
    }
    
    fn is_leaf(&self) -> bool {
        self.left.is_none() || self.right.is_none()
    }
    
    fn change(&mut self, p: usize, x: i32) {
        if self.is_leaf() {
            self.top2 = Top2 { one: (x, 1), two: (0, 0) }
        }
        else {
            let left = self.left.as_mut().unwrap();
            let right = self.right.as_mut().unwrap();
            let mid = (self.first + self.last) / 2;
            if p < mid {
                left.change(p, x)
            }
            else {
                right.change(p, x)
            }
            self.top2 = left.top2.union(&right.top2)
        }
    }
    
    fn range_top2(&self, first: usize, last: usize) -> Top2 {
        let mid = (self.first + self.last) / 2;
        if first <= self.first && self.last <= last {
            self.top2
        }
        else if mid <= first {
            self.right.as_ref().unwrap().range_top2(first, last)
        }
        else if mid >= last {
            self.left.as_ref().unwrap().range_top2(first, last)
        }
        else {
            let top2_left = self.left.as_ref().unwrap().range_top2(first, last);
            let top2_right = self.right.as_ref().unwrap().range_top2(first, last);
            top2_left.union(&top2_right)
        }
    }
    
    fn create(A: &Vec<i32>) -> Node {
        Node::new(0, A.len(), A)
    }
}


//////////////////// Query ////////////////////

enum Query {
    Change(usize, i32),
    Top2Range(usize, usize),
}

impl Query {
    fn read() -> Query {
        let v: Vec<usize> = read_vec();
        if v[0] == 1 {
            Query::Change(v[1], v[2] as i32)
        }
        else {
            Query::Top2Range(v[1], v[2])
        }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<i32>) {
    let v = read_vec();
    let Q = v[1];
    let A = read_vec();
    (Q, A)
}

fn F(Q: usize, A: Vec<i32>) {
    let mut tree = Node::create(&A);
    for _ in 0..Q {
        match Query::read() {
            Query::Change(p, x) => tree.change(p-1, x),
            Query::Top2Range(l, r) => {
                let top2 = tree.range_top2(l-1, r);
                println!("{}", top2.two.1)
            }
        }
    }
}

fn main() {
    let (Q, A) = read_input();
    F(Q, A)
}