AtCoder Beginner Contest 338 D

https://atcoder.jp/contests/abc338/tasks/abc338_d

一歩ずつ進みます。例1だとまず1から3ですが、封鎖した橋が1か2なら長さ1、3なら長さ2です。次に3から2ですが、封鎖した橋が1か3なら長さ1、2なら長さ2です。このように同じ長さが続くので、セグメント木を作って、ある範囲に同じ長さを足します。

// Island Tour
#![allow(non_snake_case)]

use std::cmp::{min, 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 ////////////////////

const INF: i64 = 10_i64.pow(18);

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

impl SegmentTree {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(m: usize) -> SegmentTree {
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<i64> = vec![0; n*2-1];
        for i in n+m-1..n*2-1 {
            v[i] = INF
        }
        SegmentTree { n, v }
    }
    
    fn add_range(&mut self, i: usize, j: usize, v_: usize) {
        let v: i64 = v_ as i64;
        self.add(j, v);
        self.sub(i-1, v)
    }
    
    // add v to [1, right]
    fn add(&mut self, right: usize, v: i64) {
        let mut i = right + self.n;
        if right == self.n {
            self.v[0] += v
        }
        while i > 1 {
            if (i & 1) == 1 {
                self.v[i-2] += v
            }
            i >>= 1
        }
    }
    
    // subtract v to [1, right]
    fn sub(&mut self, right: usize, v: i64) {
        let mut i = right + self.n;
        if right == self.n {
            self.v[0] -= v
        }
        while i > 1 {
            if (i & 1) == 1 {
                self.v[i-2] -= v
            }
            i >>= 1
        }
    }
    
    fn min(&self) -> i64 {
        self.min_core(0)
    }
    
    fn min_core(&self, i: usize) -> i64 {
        if i >= self.n - 1 {
            self.v[i]
        }
        else {
            self.v[i] + min(self.min_core(i*2+1), self.min_core(i*2+2))
        }
    }
}


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

fn read_input() -> (usize, Vec<usize>) {
    let v = read_vec();
    let N = v[0];
    let X = read_vec();
    (N, X)
}

fn F(N: usize, X: Vec<usize>) -> i64 {
    let mut raq = SegmentTree::create(N);
    for i in 0..X.len()-1 {
        let u = min(X[i], X[i+1]);
        let v = max(X[i], X[i+1]);
        if u == 1 {
            raq.add_range(1, v-1, N-v+1);
            raq.add_range(v, N, v-1);
        }
        else if v == N {
            raq.add_range(1, u-1, N-u);
            raq.add_range(u, N-1, u);
            raq.add_range(N, N, N-u)
        }
        else {
            raq.add_range(1, u-1, v-u);
            raq.add_range(u, v-1, N-v+u);
            raq.add_range(v, N, v-u)
        }
    }
    raq.min()
}

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