アルゴリズムと数学 039

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

セグメント木を使うとVecの操作だけで済むので簡単ですね。

// 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()
}


//////////////////// Tree ////////////////////

struct Tree {
    depth: usize,
    v: Vec<i32>
}

impl Tree {
    fn is_leaf(&self, i: usize) -> bool {
        ((i >> (self.depth-1)) & 1) == 1
    }
    
    fn first(&self, i: usize) -> usize {
        if i == 1 {
            0
        }
        else {
            let bit = i & 1;
            self.first(i >> 1) + bit * self.length(i)
        }
    }
    
    fn mid(&self, i: usize) -> usize {
        self.first(i) + self.length(i) / 2
    }
    
    fn last(&self, i: usize) -> usize {
        self.first(i) + self.length(i)
    }
    
    fn length_core(&self, i: usize, depth: usize) -> usize {
        if i == 1 {
            1 << depth
        }
        else {
            self.length_core(i >> 1, depth - 1)
        }
    }
    
    fn length(&self, i: usize) -> usize {
        self.length_core(i, self.depth - 1)
    }
    
    fn left(&self, i: usize) -> usize {
        i << 1
    }
    
    fn right(&self, i: usize) -> usize {
        (i << 1) + 1
    }
    
    fn value(&self, i: usize) -> i32 {
        self.value_core(i + (1 << (self.depth - 1)))
    }
    
    fn value_core(&self, i: usize) -> i32 {
        if i == 1 {
            self.v[i-1]
        }
        else {
            self.v[i-1] + self.value_core(i >> 1)
        }
    }
    
    fn add_core(&mut self, i: usize, first: usize, last: usize, value: i32) {
        let mid = self.mid(i);
        if first <= self.first(i) && self.last(i) <= last {
            self.v[i-1] += value;
            return
        }
        if first < mid {
            self.add_core(self.left(i), first, last, value);
        }
        if mid < last {
            self.add_core(self.right(i), first, last, value);
        }
    }
    
    fn add(&mut self, first: usize, last: usize, value: i32) {
        self.add_core(1, first, last, value)
    }
    
    fn create(N: usize) -> Tree {
        let depth = Tree::calc_depth(N);
        let v = (0..(1<<depth)).map(|_| 0).collect::<Vec<i32>>();
        Tree { depth, v }
    }
    
    fn calc_depth(N: usize) -> usize {
        if N == 1 {
            1
        }
        else {
            1 + Tree::calc_depth((N - 1) / 2 + 1)
        }
    }
}


//////////////////// 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 = Tree::create(N);
    for _ in 0..Q {
        let (L, R, X) = read_query();
        tree.add(L, R, X)
    }
    
    let v = (0..N).map(|i| tree.value(i)).collect::<Vec<i32>>();
    (0..N-1).map(|i| compare(v[i], v[i+1])).collect::<String>()
}

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