AtCoder Beginner Contest 352 D

https://atcoder.jp/contests/abc352/tasks/abc352_d

インデックスをPの要素の大きさで並べ替えて、幅Kの中に入るインデックスの最大と最小の差を調べます。

// Permutation Subsequence
#![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: usize = 10000000;

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

impl SegmentTree {
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(B: Vec<usize>) -> SegmentTree {
        let m = B.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<(usize, usize)> = vec![(0, 0); n*2-1];
        for i in n-1..n-1+m {
            v[i] = (B[i+1-n], B[i+1-n])
        }
        for i in (0..n-1).rev() {
            v[i] = (min(v[i*2+1].0, v[i*2+2].0),
                    max(v[i*2+1].1, v[i*2+2].1))
        }
        SegmentTree { n, v }
    }
    
    fn range(&self, i: usize, j: usize) -> (usize, usize) {
        self.query(i, j, 0, 0, self.n)
    }
    
    fn query(&self, i: usize, j: usize,
                    k: usize, l: usize, r: usize) -> (usize, usize) {
        if r <= i || j <= l {
            (INF, 0)
        }
        else if i <= l && r <= j {
            self.v[k]
        }
        else {
            let mid = (l + r) / 2;
            let m1 = self.query(i, j, k*2+1, l, mid);
            let m2 = self.query(i, j, k*2+2, mid, r);
            (min(m1.0, m2.0), max(m1.1, m2.1))
        }
    }
}


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

fn read_input() -> (usize, Vec<usize>) {
    let v = read_vec();
    let K = v[1];
    let P: Vec<usize> = read_vec();
    (K, P)
}

fn create_tree(P: Vec<usize>) -> SegmentTree {
    let mut v: Vec<(usize, usize)> = P.into_iter().enumerate().collect();
    v.sort_by_key(|&(_, e)| e);
    let Q: Vec<usize> = v.into_iter().map(|(i, _)| i).collect();
    SegmentTree::create(Q)
}

fn F(K: usize, P: Vec<usize>) -> usize {
    let N = P.len();
    let tree = create_tree(P);
    let mut min_range = N;
    for first in 0..N-K+1 {
        let (min_index, max_index) = tree.range(first, first+K);
        min_range = min(min_range, max_index-min_index)
    }
    min_range
}

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