Dynamic Range Minimum Queries

warning: unused import: `max`
 --> input/code.rs:1:16
  |
1 | use std::cmp::{max, min};
  |                ^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `HashMap`, `HashSet`
 --> input/code.rs:2:24
  |
2 | use std::collections::{HashMap, HashSet};
  |                        ^^^^^^^  ^^^^^^^

warning: 2 warnings emitted

use std::cmp::{max, min};
use std::collections::{HashMap, HashSet};
use std::io::{self, Read};

macro_rules! input {
    ($it: expr) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: expr, $T: ty) => {
        $it.next().unwrap().parse::<$T>().unwrap()
    };
}
/*
mod classes;
mod homework;

fn main() {
    // println!("{}", "-".repeat(20));
    // classes::c07::task4();
    homework::hw3::task1();
    // println!("{}", "-".repeat(20));
}
// */

fn closest_pow_of_2(n: &usize) -> usize {
    let mut x = 1;
    while x<*n {
        x*=2;
    }
    x
}

fn min_query(mut a: usize, mut b:usize, t: &Vec<usize>) -> usize {
    let n=t.len()/2;
    a+=n-1; // input is 1 indexed
    b+=n-1; // input is 1 indexed
    let mut rtn = 10usize.pow(10);
    while a<= b {
        if a%2 == 1 {
            rtn = min(t[a], rtn);
            a+=1;
        }
        if b%2 == 0 {
            rtn = min(t[b], rtn);
            b-=1;
        }
        a/=2;
        b/=2;
    }
    rtn
}

fn update(mut k: usize, u:usize, t: &mut Vec<usize>) {
    let n=t.len()/2;
    k= k + n - 1; // input is 1 indexed
    t[k] = u;
    k/=2;
    while k>0 {
        t[k] = min(t[k*2], t[k*2+1]);
        k/=2;
    }
}

fn main() {
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();

    let mut it = buf.split_whitespace();

    let  (n, mut q): (usize, usize) = (input!(it), input!(it));

    let n_pow_2 = closest_pow_of_2(&n);

    let mut t = vec![10usize.pow(10); 2*n_pow_2];

    for i in 0..n {
        t[n_pow_2+i] = input!(it);
    }

    for i in (0..n_pow_2).rev() {
        t[i] = min(t[2 * i], t[2 * i + 1]);
    }

    while q>0 {
        q-=1;
        let  (op, a, b): (usize, usize, usize) = (input!(it), input!(it), input!(it));
        match op {
            1 => update(a, b, &mut t),
            2 => println!("{}", min_query(a, b, &mut t)),
            _ => todo!(),
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED