AtCoder Beginner Contest 436 F

https://atcoder.jp/contests/abc436/tasks/abc436_f

これはよくある和の順序を変えれば答えられる問題です。問題文では範囲を指定してそれからシャッター時間？を変えていますが、まずシャッター時間を固定します。入力例1だと、まず1だけ写るようにします。これは1通りです。次に2も写るようにします。1だけはもう考慮してあるので、必ず2が入るようにします。2より小さいものは左に1つ、右にはないので、(1+1)*(0+1)=2通りあります。次に3を追加すると、3の左になくて右に2つあるので3通り、最後に4を追加すると、(2+1)*(1+1)=6通りあり、合計で12通りです。
範囲に何個あるかは木を作ればすぐに求められます。

// Starry Landscape Photo
#![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()
}


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

type Range = (usize, usize);
type Node = usize;
type NodeRange = (usize, usize, usize);

struct SegmentTree {
    n: usize,
    v: Vec<Node>,
}

impl SegmentTree {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn new(N: usize) -> SegmentTree {
        let n = SegmentTree::ceil_two_pow(N);
        let v: Vec<Node> = vec![0; n*2-1];
        SegmentTree { n, v }
    }
    
    fn update(&mut self, i: usize) {
        self.update_core(i, (0, self.n, 0))
    }
    
    fn update_core(&mut self, i: usize, (first, last, n): NodeRange) {
        if last - first == 1 {
            self.v[n] = 1
        }
        else {
            let mid = (first + last) / 2;
            if i < mid {
                self.update_core(i, (first, mid, n*2+1))
            }
            else {
                self.update_core(i, (mid, last, n*2+2))
            }
            self.v[n] = self.v[n*2+1] + self.v[n*2+2]
        }
    }
    
    fn count(&self, rng: &Range) -> usize {
        if rng.0 == rng.1 {
            0
        }
        else {
            self.count_core(rng, (0, self.n, 0))
        }
    }
    
    fn count_core(&self, rng: &Range, (first, last, n): NodeRange) -> usize {
        if last <= rng.0 || rng.1 <= first {
            0   // このノードは範囲外
        }
        else if rng.0 <= first && last <= rng.1 {
            self.v[n]   // このノードを覆っている
        }
        else {
            let mid = (first + last) / 2;
            let mut s: usize = 0;
            if rng.0 < mid {
                s += self.count_core(rng, (first, mid, n*2+1))
            }
            if mid < rng.1 {
                s += self.count_core(rng, (mid, last, n*2+2))
            }
            s
        }
    }
}


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

fn read_input() -> Vec<usize> {
    let _N: usize = read();
    let B = read_vec::<usize>().into_iter().map(|b| b-1).collect();
    B
}

fn inverse(B: &Vec<usize>) -> Vec<usize> {
    let N = B.len();
    let mut C: Vec<usize> = vec![0; N];
    for i in 0..N {
        C[B[i]] = i
    }
    C
}

fn F(B: Vec<usize>) -> usize {
    let N = B.len();
    let C = inverse(&B);
    let mut s: usize = 0;
    let mut tree = SegmentTree::new(N);
    for c in C {
        let n1 = tree.count(&(0, c));
        let n2 = tree.count(&(c, N));
        s += (n1 + 1) * (n2 + 1);
        tree.update(c)
    }
    s
}

fn main() {
    let B = read_input();
    println!("{}", F(B))
}