結果

問題 No.875 Range Mindex Query
ユーザー wesriverywesrivery
提出日時 2019-09-13 22:41:14
言語 Rust
(1.77.0)
結果
AC  
実行時間 254 ms / 2,000 ms
コード長 5,952 bytes
コンパイル時間 752 ms
コンパイル使用メモリ 143,564 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2023-09-17 14:52:44
合計ジャッジ時間 4,841 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 213 ms
9,268 KB
testcase_12 AC 170 ms
7,388 KB
testcase_13 AC 152 ms
10,952 KB
testcase_14 AC 148 ms
10,360 KB
testcase_15 AC 206 ms
11,232 KB
testcase_16 AC 252 ms
11,220 KB
testcase_17 AC 254 ms
11,520 KB
testcase_18 AC 245 ms
11,500 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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();
}
0