Water Tank の解説

座圧して、セグ木で終わり！

fn main() {
    input! {
        n: usize,
        mut h: [usize; n]
    }
    h.push(0);
    let comp = CoordinateCompression::new(&h);
    let mut seg = Segtree::<Max<usize>>::new(n + 1);
    let mut ans = vec![0];
    let mut a = vec![];
    for i in 1..=n {
        let target = h[i - 1];
        let id = comp.get(target).unwrap();
        let pre = seg.prod(id..);
        let base = ans[pre];
        let bonus = target * (i - pre);
        ans.push(base + bonus);
        a.push(base + bonus + 1);
        seg.set(id, i);
    }
    println!("{}" ,a.iter().join(" "));
}