アルゴリズムと数学 039（2）

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aj

ふつうに二分木を作ろうと思って書いたものの、コンパイラが通らずに苦労していたのですが、Bingに書かせてみたらちょっと違うものができてきたもののコンパイラが通るので、これを元に仕上げました。ポイントはどこなんでしょうね。
なぜかセグメント木より速いです。

// Snowy Days
#![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()
}


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

struct Node {
    first: usize,
    last: usize,
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>
}

impl Node {
    fn new(first: usize, last: usize, value: i32) -> Self {
        Self {
            first,
            last,
            value,
            left: None,
            right: None,
        }
    }
    
    fn is_leaf(&self) -> bool {
        return self.left.is_none()
    }
    
    fn traverse_inorder(&self, value: i32) -> Vec<i32> {
        let mut v: Vec<i32> = Vec::new();
        if let Some(left) = &self.left {
            let mut v1 = left.traverse_inorder(self.value + value);
            v.append(&mut v1)
        }
        if self.is_leaf() {
            v.push(self.value + value)
        }
        if let Some(right) = &self.right {
            let mut v2 = right.traverse_inorder(self.value + value);
            v.append(&mut v2)
        }
        v
    }
    
    fn add(&mut self, first: usize, last: usize, value_to_add: i32) {
        if first <= self.first && last >= self.last {
            self.value += value_to_add;
            return
        }
        
        if let Some(left) = &mut self.left {
            if first < left.last {
                left.add(first, last, value_to_add);
            }
        }
        
        if let Some(right) = &mut self.right {
            if last > right.first {
                right.add(first, last, value_to_add);
            }
        }
    }
    
    fn create(first: usize, last: usize, value: i32) -> Option<Box<Node>> {
        if last - first == 1 {
            let node = Node { first, last, value, left: None, right: None };
            Some(Box::new(node))
        }
        else {
            let mid = (first + last) / 2;
            let mut node = Node::new(first, last, value);
            node.left = Node::create(first, mid, value);
            node.right = Node::create(mid, last, value);
            Some(Box::new(node))
        }
    }
}


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

type Query = (usize, usize, i32);

fn read_query() -> Query {
    let v = read_vec();
    let L: usize = v[0] - 1;
    let R: usize = v[1];
    let X: i32 = v[2] as i32;
    (L, R, X)
}

fn read_input() -> (usize, usize) {
    let v = read_vec();
    let N: usize = v[0];
    let Q: usize = v[1];
    (N, Q)
}

fn compare(a: i32, b: i32) -> char {
    if a < b {
        '<'
    }
    else if a > b {
        '>'
    }
    else {
        '='
    }
}

fn f(N: usize, Q: usize) -> String {
    let mut tree = Node::create(0, N, 0).unwrap();
    for _ in 0..Q {
        let (L, R, X) = read_query();
        tree.add(L, R, X)
    }
    
    let v = tree.traverse_inorder(0);
    (0..N-1).map(|i| compare(v[i], v[i+1])).collect::<String>()
}

fn main() {
    let (N, Q) = read_input();
    println!("{}", f(N, Q))
}