Dynamic Range Minimum Queries

#![allow(unused)]

use std::io;

fn take_tuple() -> (usize, usize) {
    let mut input: String = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap());
    (it.next().unwrap(), it.next().unwrap())
}

fn take_triple() -> (usize, usize, usize) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap());
    (it.next().unwrap(), it.next().unwrap(), it.next().unwrap())
}

fn take_vector() -> Vec<usize> {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let arr: Vec<usize> = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap())
        .collect();
    return arr;
}

fn build_segment_tree(arr: &Vec<usize>, n2: &usize) -> Vec<usize> {
    let mut tree: Vec<usize> = vec![usize::MAX; n2 * 2];
    let mut k = *n2;

    for i in 0..arr.len() {
        let mut parent = (k / 2);
        tree[k] = arr[i];
        while parent >= 1 {
            tree[parent] = usize::min(tree[2 * parent], tree[2 * parent + 1]);
            parent = (parent / 2);
        }
        k += 1;
    }
    // println!("{:?}", tree);
    tree
}

fn update_tree(tree: &mut Vec<usize>, mut k: usize, u: usize, n2: &usize) {
    k += *n2;
    tree[k] = u as usize;
    let mut parent = k / 2;
    while parent >= 1 {
        tree[parent] = usize::min(tree[2 * parent], tree[2 * parent + 1]);
        parent = (parent / 2);
    }
    // println!("{:?}", tree);
}

fn find_min(tree: &Vec<usize>, mut a: usize, mut b: usize, n2: &usize) {
    a += *n2;
    b += *n2;
    let mut c_min = usize::MAX;
    while (a < b && b > 0) {
        // print!("looking at {a}, {b}");
        if a % 2 == 1 {
            c_min = usize::min(tree[a + 1], c_min);
            // print!(" [a]: {}, [a+1]: {}", tree[a], tree[a + 1]);
        }
        if b % 2 == 0 {
            c_min = usize::min(tree[b - 1], c_min);
            // print!(" [b]: {}, [b-1]: {}", tree[b], tree[b - 1]);
        }
        a = (a / 2);
        b = (b / 2);
        // print!(". new min: {}", c_min);
        // println!("");
    }
    c_min = usize::min(tree[a], c_min);
    c_min = usize::min(tree[b], c_min);
    // println!("min is: {c_min}");
    println!("{c_min}");
    // println!("");
}

fn main() {
    let (n, q): (usize, usize) = take_tuple();
    let mut arr: Vec<usize> = take_vector();
    let n2 = arr.len().next_power_of_two();

    let mut tree: Vec<usize> = build_segment_tree(&arr, &n2);
    for _ in 0..q {
        let (command, a, b) = take_triple();
        if command == 1 {
            update_tree(&mut tree, a - 1, b, &n2);
        } else {
            // println!("looking for [{}-{}]", a, b);
            find_min(&tree, a - 1, b - 1, &n2);
        }
    }
}

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER