#379143 (Rust) No.875 Range Mindex Query

• 問題: No.875 Range Mindex Query
• ユーザー: wesrivery
• 提出日時: 2019-09-13 22:41:14
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 237 ms / 2,000 ms
• コード長: 5,952 bytes
• コンパイル時間: 11,942 ms
• コンパイル使用メモリ: 377,736 KB
• 実行使用メモリ: 11,396 KB
• 最終ジャッジ日時: 2024-07-04 10:06:22
• 合計ジャッジ時間: 15,541 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	181 ms; 9,388 KB
testcase_12	AC	146 ms; 7,388 KB
testcase_13	AC	133 ms; 10,852 KB
testcase_14	AC	124 ms; 10,196 KB
testcase_15	AC	187 ms; 11,116 KB
testcase_16	AC	212 ms; 11,120 KB
testcase_17	AC	232 ms; 11,388 KB
testcase_18	AC	237 ms; 11,396 KB

ソースコード

// use std::cell::{Ref, RefMut, RefCell};
// use std::sync::{Arc, Mutex};

#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($( { splits.next().unwrap().parse::<$t>().unwrap() },)*)
    }}
}


#[allow(unused_macros)]
macro_rules! invec {
    ( $ t : ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(n) => s
                .trim()
                .split_whitespace()
                .map(|s| s.parse::<$t>().unwrap())
                .collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }};
}

enum SegmentTree {
    Leaf(u32),
    Node(u32, usize, Box<SegmentTree>, Box<SegmentTree>),
}

impl SegmentTree {
    fn query(&self, from: usize, to: usize, n: usize) -> (u32, usize) {
        match self {
            SegmentTree::Leaf(v) => (*v, 0),
            SegmentTree::Node(v, index, left, right) => {
                if to - from + 1 == n {
                    return (*v, *index);
                }

                let boundary = n / 2;
                if from < boundary && boundary <= to {
                    let right_to = to - boundary;
                    let (lval, lindex) = left.as_ref().query(from, boundary - 1, boundary);
                    let (rval, rindex) = right.as_ref().query(0, right_to, n - boundary);
                    let rindex = rindex + boundary;
                    if lval < rval {
                        return (lval, lindex);
                    } else {
                        return (rval, rindex);
                    }
                }

                if from < boundary {
                    return left.as_ref().query(from, to, boundary);
                } else {
                    // println!("ltmp = {}, rtmp = {}", ltmp, rtmp);
                    let right_from = from - boundary;
                    let right_to = to - boundary;
                    let (rval, rindex) = right.as_ref().query(right_from, right_to, n - boundary);
                    return (rval, rindex + boundary);
                }
            }
        }
    }

    fn update(&mut self, index: usize, value: u32, n: usize) {
        match self {
            SegmentTree::Leaf(ref mut v) => {
                // println!("updated leaf val = {}", value);
                *v = value;
                // (*v)[index] = value;
                // SegmentTree::Leaf(index, v)
                return;
            },
            SegmentTree::Node(ref mut val, ref mut ind, ref mut left, ref mut right) => {

                let boundary = n / 2;
                if index < boundary {
                    // println!("updating left : index = {}, value = {}", index, value);
                    left.update(index, value, boundary);
                    // println!("updated left : value = {}, fact value = {}", value, left.val());
                } else {
                    // let right_index = index - boundary;
                    // println!("updating right : index = {}, value = {}", index, value);
                    right.update(index - boundary, value, n - boundary);
                    // println!("updated right : value = {}, fact value = {}", value, right.val());
                }

                let (new_val, new_index) = 
                    if left.val() <=  right.val() {
                        (left.val(), left.ind())
                    } else {
                        (right.val(), right.ind() + boundary)
                    };

                *val = new_val;
                *ind = new_index;
            }
        }
    }

    fn new(a: &[u32], n: usize) -> SegmentTree {
        if n == 1 {
            // println!("new(leaf) : n = {}, index = {}", n, index);
            SegmentTree::Leaf(a[0], )
        } else {

            // println!("new : n = {}, index = {}", n, index);

            let half = n / 2;
            let left = SegmentTree::new(&a[0..half], half);
            let right = SegmentTree::new(&a[half..n], n - half);

            // println!("new : n = {}, index = {} leftright end", n, index);

            // let left_value = left.val;
            // let right_value = right.val;
            let (i, val) =
                if left.val() <= right.val() {
                    (left.ind(), left.val())
                } else {
                    (right.ind() + half, right.val())
                };
            // println!("i updated");

            SegmentTree::Node(val, i, Box::new(left), Box::new(right))
        }
    }

    fn val(&self) -> u32 {
        match *self {
            SegmentTree::Node(v, _, _, _) => v,
            SegmentTree::Leaf(v) => v,
        }
    }

    fn ind(&self) -> usize {
        match *self {
            SegmentTree::Node(_, i, _, _) => i,
            SegmentTree::Leaf(_) => 0,
        }
    }
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n, q) = input!(usize, usize);
    let a = invec!(u32);
    
    // println!("kokoko");
    // let mtx = Arc::new(Mutex::new(a));
    let mut tree = SegmentTree::new(&a[..], n);
    // println!("kokoko");

    for _ in 0..q {
        let (op, l, r) = input!(u8, usize, usize);
        let l = l - 1;
        let r = r - 1;

        match op {
            1 => {
                let (ltmp, _) = tree.query(l, l, n);
                let (rtmp, _) = tree.query(r, r, n);
                // println!("ltmp = {}, rtmp = {}", ltmp, rtmp);
                (&mut tree).update(l, rtmp, n);
                // println!("swapping {}, {}...", l, r);
                (&mut tree).update(r, ltmp, n);
            },
            2 => {
                let res = tree.query(l, r, n);
                println!("{}", res.1 + 1);
            },
            _ => {},
        }
    }
}

fn main() {
    solve();
}