結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー cra77756176
提出日時 2022-12-13 23:26:09
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 237 ms / 2,000 ms
コード長 3,087 bytes
記録
コンパイル時間 14,177 ms
コンパイル使用メモリ 379,648 KB
実行使用メモリ 16,128 KB
最終ジャッジ日時 2024-11-07 16:57:25
合計ジャッジ時間 18,225 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

struct RangeMinimumTree<T: Clone + PartialOrd> {
    n: usize,
    v: Vec<Option<(usize, T)>>,
}

impl<T: Clone + PartialOrd> RangeMinimumTree<T> {
    fn new(n: usize) -> Self {
        let mut n2p = 1;
        while n2p < n {
            n2p <<= 1;
        }
        let n = n2p;

        Self {
            n,
            v: vec![None; 2 * n],
        }
    }

    fn update(&mut self, i: usize, x: &T) {
        let mut i_inner = self.n - 1 + i;
        self.v[i_inner] = Some((i, x.clone()));
        while i_inner > 0 {
            i_inner = (i_inner - 1) / 2;
            self.v[i_inner] =
                Self::optional_min(&self.v[i_inner * 2 + 1], &self.v[i_inner * 2 + 2]);
        }
    }

    fn query(&self, l_whole: usize, r_whole: usize) -> (usize, T) {
        self.query_sub(l_whole, r_whole, 0, 0, self.n).unwrap()
    }

    fn query_sub(
        &self,
        l_whole: usize,
        r_whole: usize,
        k: usize,
        l: usize,
        r: usize,
    ) -> Option<(usize, T)> {
        if r <= l_whole || r_whole <= l {
            None
        } else if l_whole <= l && r <= r_whole {
            self.v[k].clone()
        } else {
            let min_l = self.query_sub(l_whole, r_whole, k * 2 + 1, l, (l + r) / 2);
            let min_r = self.query_sub(l_whole, r_whole, k * 2 + 2, (l + r) / 2, r);

            Self::optional_min(&min_l, &min_r).map_or_else(|| unreachable!(), Some)
        }
    }

    fn optional_min(a: &Option<(usize, T)>, b: &Option<(usize, T)>) -> Option<(usize, T)> {
        match (a, b) {
            (Some(a), Some(b)) => {
                if a.1 < b.1 {
                    Some(a.clone())
                } else {
                    Some(b.clone())
                }
            }
            (Some(a), None) => Some(a.clone()),
            (None, Some(b)) => Some(b.clone()),
            (None, None) => None,
        }
    }
}

impl<T: Clone + PartialOrd> std::ops::Index<usize> for RangeMinimumTree<T> {
    type Output = Option<(usize, T)>;
    fn index(&self, i: usize) -> &Self::Output {
        let i = self.n - 1 + i;
        &self.v[i]
    }
}

fn main() {
    let mut xx = String::new();
    std::io::Read::read_to_string(&mut std::io::stdin(), &mut xx).ok();
    let xx: Vec<usize> = xx.split_whitespace().flat_map(str::parse).collect();

    let n = xx[0];
    let aa: Vec<usize> = xx.clone().into_iter().skip(2).take(n).collect();
    let qq: Vec<usize> = xx.into_iter().skip(n + 2).collect();

    let mut tree = RangeMinimumTree::new(n);
    for (i, a) in aa.iter().enumerate() {
        tree.update(i, a);
    }

    for q in qq.chunks(3) {
        if let &[t, l, r] = q {
            let l = l - 1;
            let r = r - 1;
            match t {
                1 => {
                    let v_l = tree[l].unwrap().1;
                    let v_r = tree[r].unwrap().1;
                    tree.update(l, &v_r);
                    tree.update(r, &v_l);
                }
                2 => println!("{}", tree.query(l, r + 1).0 + 1),
                _ => unreachable!(),
            }
        }
    }
}
0