結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー wesrivery
提出日時 2019-09-07 01:38:03
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 4,721 bytes
コンパイル時間 11,791 ms
コンパイル使用メモリ 391,680 KB
実行使用メモリ 793,600 KB
最終ジャッジ日時 2024-06-25 00:39:08
合計ジャッジ時間 14,249 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other MLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[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(),
        }
    }};
}

struct Leaf {
    index: usize,
    value: u32,
}

struct Node {
    from: usize,
    to: usize,
    value: u32,
    index: usize,
    left: Box<SegmentTree>,
    right: Box<SegmentTree>,
}

enum SegmentTree {
    Leaf(Leaf),
    Node(Node),
}

impl SegmentTree {
    fn query(&self, from: usize, to: usize) -> (usize, u32) {
        match self {
            SegmentTree::Leaf(leaf) => (leaf.index, leaf.value),
            SegmentTree::Node(node) => {
                let boundary = (node.from + node.to) / 2;
                if from <= boundary && boundary < to {
                    let (lindex, lval) = node.left.as_ref().query(from, boundary);
                    let (rindex, rval) = node.right.as_ref().query(boundary + 1, to);
                    if lval < rval {
                        return (lindex, lval);
                    } else {
                        return (rindex, rval);
                    }
                }

                if from <= boundary {
                    return node.left.as_ref().query(from, to);
                } else {
                    return node.right.as_ref().query(from, to);
                }
            }
        }
    }

    fn update(&mut self, index: usize, value: u32) {
        match self {
            SegmentTree::Leaf(leaf) => {
                leaf.index = index;
                leaf.value = value;
                return;
            },
            SegmentTree::Node(node) => {

                let boundary = (node.from + node.to) / 2;
                if index <= boundary {
                    node.left.as_mut().update(index, value);
                } else {
                    node.right.as_mut().update(index, value);
                }

                let left = node.left.as_ref();
                let right = node.right.as_ref();

                if left.val() <= right.val() {
                    node.index = left.ind();
                    node.value = left.val();
                } else {
                    node.index = right.ind();
                    node.value = right.val();
                };
            }
        }
    }

    fn new(v: &Vec<u32>, from: usize, to: usize) -> SegmentTree {
        if from == to {
            return SegmentTree::Leaf(Leaf { index: from,
                          value: v[from],
            });
        }

        let boundary = from + to / 2;
        let left = SegmentTree::new(&v, from, boundary);
        let right = SegmentTree::new(&v, boundary + 1, to);

        let (value, index) =
            if left.val() <= right.val() {
                (left.val(), left.ind())
            } else {
                (right.val(), right.ind())
            };

        return SegmentTree::Node(Node { from: from,
                             to: to,
                             value: value,
                             index: index,
                             left: Box::new(left),
                             right: Box::new(right),
        });
    }

    fn val(&self) -> u32 {
        match self {
            SegmentTree::Node(node) => node.value,
            SegmentTree::Leaf(leaf) => leaf.value,
        }
    }

    fn ind(&self) -> usize {
        match self {
            SegmentTree::Node(node) => node.index,
            SegmentTree::Leaf(leaf) => leaf.index,
        }
    }
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n, q) = input!(usize, usize);
    let a = invec!(u32);
    
    let mut tree = SegmentTree::new(&a, 0, n - 1);

    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);
                let (_, rtmp) = tree.query(r, r);
                (&mut tree).update(l, rtmp);
                (&mut tree).update(r, ltmp);
            },
            2 => {
                println!("{}", tree.query(l, r).0 + 1);
            },
            _ => {},
        }
    }
}

fn main() {
    solve();
}
0