AtCoder Beginner Contest 372 D

https://atcoder.jp/contests/abc372/tasks/abc372_d

jより左で最も右のH_jより高いビルの位置を探せばよいです。そういう木を作ります。

//  Buildings 
#![allow(non_snake_case)]

use std::cmp::max;


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


//////////////////// Segment Tree ////////////////////

type Value = i32;

struct SegmentTree {
    n: usize,   // 2-pow
    max: Vec<Value>,
}

impl SegmentTree {
    fn update(&mut self, i: usize, x: Value) {
        let mut k = i + self.n - 1;
        self.max[k] = x;
        while k > 0 {
            k = (k - 1) / 2;
            self.max[k] = max(self.max[k*2+1], self.max[k*2+2])
        }
    }
    
    fn find_rightmost_greater(&mut self, j: usize, h: Value) -> usize {
        self.find_rightmost_greater_core(j, h, 0, 0, self.n)
    }
    
    fn find_rightmost_greater_core(&mut self, j: usize, h: Value,
                        cell: usize, first: usize, last: usize) -> usize {
        let mid = (first + last) / 2;
        if self.max[cell] <= h {
            0
        }
        else if first >= j {
            0
        }
        else if last - first == 1 {
            first
        }
        else if mid >= j {
            self.find_rightmost_greater_core(j, h, cell*2+1, first, mid)
        }
        else if self.max[cell*2+2] <= h {
            self.find_rightmost_greater_core(j, h, cell*2+1, first, mid)
        }
        else if self.max[cell*2+1] <= h {
            self.find_rightmost_greater_core(j, h, cell*2+2, mid, last)
        }
        else {
            let p = self.find_rightmost_greater_core(j, h, cell*2+2, mid, last);
            if p > 0 {
                p
            }
            else {
                self.find_rightmost_greater_core(j, h, cell*2+1, first, mid)
            }
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(H: &Vec<Value>) -> SegmentTree {
        let m = H.len();
        let n = SegmentTree::ceil_two_pow(m);
        let max: Vec<Value> = vec![0; n*2-1];
        let mut tree = SegmentTree { n, max };
        for (i, &e) in H.iter().enumerate() {
            tree.update(i, e)
        }
        tree
    }
}


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

fn read_input() -> Vec<Value> {
    let _N: usize = read();
    let H: Vec<Value> = read_vec();
    H
}

fn F(H: Vec<Value>) {
    let N = H.len();
    let mut tree = SegmentTree::create(&H);
    let mut v: Vec<Value> = vec![0; N];
    for (i, h) in H.into_iter().enumerate() {
        let k = tree.find_rightmost_greater(i, h);
        if k > 0 {
            v[k-1] += 1
        }
    }
    
    let mut acc: Vec<Value> = vec![0; N+1];
    for i in (0..N).rev() {
        acc[i] = acc[i+1] + v[i]
    }
    
    let mut w: Vec<Value> = vec![0; N];
    for i in 0..N {
        w[i] = (N - i - 1) as i32 - acc[i]
    }
    
    println!("{}", w.iter().map(|&e| e.to_string()).
                        collect::<Vec<String>>().join(" "))
}

fn main() {
    let H = read_input();
    F(H)
}