結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー wass80
提出日時 2020-08-03 17:47:20
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 194 ms / 2,000 ms
コード長 3,613 bytes
記録
コンパイル時間 21,849 ms
コンパイル使用メモリ 386,740 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-09-13 11:25:54
合計ジャッジ時間 17,437 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::cmp`
   --> src/main.rs:126:9
    |
126 |     use std::cmp;
    |         ^^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

ソースコード

diff #
raw source code 

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

use std::fmt::Debug;
struct SegTree<T: Clone + Debug> {
    data: Vec<T>,
    size: usize,
    zero: T,
    mapped: fn(&T, &T) -> T,
}
impl<T: Clone + Debug> SegTree<T> {
    /*
    8 elements
    1
    2         3
    4    5    6    7
    8 9  A B  C D  E F
      <-        <-
    */
    fn new(size: usize, zero: T, mapped: fn(&T, &T) -> T) -> SegTree<T> {
        let mut data = vec![];
        for _ in 0..2 * size + 1 {
            data.push(zero.clone())
        }
        SegTree {
            data: data,
            size: size,
            zero: zero,
            mapped: mapped,
        }
    }
    fn fold(&self, l: usize, r: usize) -> T {
        let mut fl = self.zero.clone();
        let mut fr = self.zero.clone();
        let mut l = l + self.size;
        let mut r = r + self.size;
        /*
            1:
            2:            3:2
            4:1    5:3    6:X    7:X

        */
        while l < r {
            if l & 1 == 1 {
                fl = (self.mapped)(&self.data[l], &fl);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                fr = (self.mapped)(&fr, &self.data[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        (self.mapped)(&fl, &fr)
    }
    fn update(&mut self, i: usize, x: T) {
        let mut i = i + self.size;
        self.data[i] = x;
        while i > 1 {
            i >>= 1;
            self.data[i] = (self.mapped)(&self.data[i << 1], &self.data[(i << 1) + 1])
        }
    }
    fn select(&self, i: usize) -> T {
        self.data[i + self.size].clone()
    }
}

fn main() {
    input! {
        n: usize, q:usize,
        a: [i64; n],
        query: [(usize, usize, usize); q]
    }
    use std::cmp;
    let inf = (1 << 31) - 1;
    let mut seg = SegTree::new(n, (inf, 0usize), |x, y| if x.0 < y.0 { *x } else { *y });
    for i in 0..n {
        seg.update(i, (a[i], i));
    }
    for (com, x, y) in query {
        if com == 1 {
            let vx = seg.select(x - 1).0;
            let vy = seg.select(y - 1).0;
            seg.update(x - 1, (vy, x - 1));
            seg.update(y - 1, (vx, y - 1));
        } else {
            println!("{}", seg.fold(x - 1, y).1 + 1);
        }
    }
}
0