#555801 (Rust) No.1234 典型RMQ

• 問題: No.1234 典型RMQ
• ユーザー: ikd
• 提出日時: 2020-09-19 16:20:35
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 223 ms / 2,000 ms
• コード長: 5,533 bytes
• コンパイル時間: 15,930 ms
• コンパイル使用メモリ: 380,476 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-11-09 02:15:07
• 合計ジャッジ時間: 20,275 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	214 ms; 5,248 KB
testcase_07	AC	174 ms; 5,248 KB
testcase_08	AC	221 ms; 5,376 KB
testcase_09	AC	197 ms; 5,248 KB
testcase_10	AC	219 ms; 5,248 KB
testcase_11	AC	212 ms; 5,248 KB
testcase_12	AC	194 ms; 5,248 KB
testcase_13	AC	176 ms; 5,248 KB
testcase_14	AC	197 ms; 5,248 KB
testcase_15	AC	193 ms; 5,248 KB
testcase_16	AC	220 ms; 5,248 KB
testcase_17	AC	199 ms; 5,248 KB
testcase_18	AC	164 ms; 5,248 KB
testcase_19	AC	223 ms; 5,376 KB
testcase_20	AC	154 ms; 5,376 KB
testcase_21	AC	213 ms; 5,248 KB
testcase_22	AC	180 ms; 5,248 KB
testcase_23	AC	180 ms; 5,248 KB
testcase_24	AC	178 ms; 5,248 KB
testcase_25	AC	178 ms; 5,248 KB
testcase_26	AC	180 ms; 5,248 KB
testcase_27	AC	1 ms; 5,248 KB
testcase_28	AC	1 ms; 5,248 KB
testcase_29	AC	1 ms; 5,248 KB

コンパイルメッセージ

warning: method `get` is never used
   --> src/main.rs:127:8
    |
38  | / impl<T, Multiply, F, Composite, Apply> LazySegmentTree<T, Multiply, F, Composite, Apply>
39  | | where
40  | |     T: Copy + std::fmt::Debug,
41  | |     Multiply: Fn(T, T) -> T,
42  | |     F: Copy + std::fmt::Debug,
43  | |     Composite: Fn(F, F) -> F,
44  | |     Apply: Fn(F, T) -> T,
    | |_________________________- method in this implementation
...
127 |       fn get(&self, i: usize) -> T {
    |          ^^^
    |
    = note: `#[warn(dead_code)]` on by default

ソースコード

pub struct ProconReader<R: std::io::Read> {
    reader: R,
}

impl<R: std::io::Read> ProconReader<R> {
    pub fn new(reader: R) -> Self {
        Self { reader }
    }
    pub fn get<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&byte| byte == b' ' || byte == b'\n' || byte == b'\r')
            .take_while(|&byte| byte != b' ' && byte != b'\n' && byte != b'\r')
            .collect::<Vec<_>>();
        std::str::from_utf8(&buf)
            .unwrap()
            .parse()
            .ok()
            .expect("Parse Error.")
    }
}

struct LazySegmentTree<T, Multiply, F, Composite, Apply> {
    n: usize,
    dat: Vec<T>,
    e: T,
    multiply: Multiply,
    laz: Vec<F>,
    id: F,
    composite: Composite,
    apply: Apply,
}

impl<T, Multiply, F, Composite, Apply> LazySegmentTree<T, Multiply, F, Composite, Apply>
where
    T: Copy + std::fmt::Debug,
    Multiply: Fn(T, T) -> T,
    F: Copy + std::fmt::Debug,
    Composite: Fn(F, F) -> F,
    Apply: Fn(F, T) -> T,
{
    fn new(
        a: &Vec<T>,
        e: T,
        multiply: Multiply,
        id: F,
        composite: Composite,
        apply: Apply,
    ) -> Self {
        let len = a.len();
        let n = len.next_power_of_two();
        let mut dat = vec![e; n * 2 - 1];
        for i in 0..len {
            dat[i + n - 1] = a[i];
        }
        for i in (0..(n - 1)).rev() {
            dat[i] = (multiply)(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
        Self {
            n,
            dat,
            e,
            multiply,
            laz: vec![id; n * 2 - 1],
            id,
            composite,
            apply,
        }
    }
    fn update_node(&mut self, i: usize, f: F) {
        self.dat[i] = (self.apply)(f, self.dat[i]);
        if i < self.n {
            self.laz[i] = (self.composite)(f, self.laz[i]);
        }
    }
    fn update_range(
        &mut self,
        range: &std::ops::Range<usize>,
        i: usize,
        i_range: std::ops::Range<usize>,
        f: F,
    ) {
        if range.end <= i_range.start || i_range.end <= range.start {
            return;
        }
        if range.start <= i_range.start && i_range.end <= range.end {
            self.update_node(i, f);
            return;
        }
        let left_child = i * 2 + 1;
        let right_child = i * 2 + 2;
        self.update_node(left_child, self.laz[i]);
        self.update_node(right_child, self.laz[i]);
        self.laz[i] = self.id;
        let m = (i_range.start + i_range.end) / 2;
        self.update_range(range, left_child, i_range.start..m, f);
        self.update_range(range, right_child, m..i_range.end, f);
        self.dat[i] = (self.multiply)(self.dat[left_child], self.dat[right_child]);
    }
    fn update(&mut self, range: std::ops::Range<usize>, f: F) {
        self.update_range(&range, 0, 0..self.n, f);
    }
    fn _fold(
        &self,
        range: &std::ops::Range<usize>,
        i: usize,
        i_range: std::ops::Range<usize>,
    ) -> T {
        if range.end <= i_range.start || i_range.end <= range.start {
            return self.e;
        }
        if range.start <= i_range.start && i_range.end <= range.end {
            return self.dat[i];
        }
        let m = (i_range.start + i_range.end) / 2;
        let left_result = self._fold(range, i * 2 + 1, i_range.start..m);
        let right_result = self._fold(range, i * 2 + 2, m..i_range.end);
        (self.apply)(self.laz[i], (self.multiply)(left_result, right_result))
    }
    fn fold(&self, range: std::ops::Range<usize>) -> T {
        self._fold(&range, 0, 0..self.n)
    }
    fn get(&self, i: usize) -> T {
        let mut i = i + self.n - 1;
        let mut res = (self.apply)(self.laz[i], self.dat[i]);
        while i > 0 {
            i = (i - 1) / 2;
            res = (self.apply)(self.laz[i], res);
        }
        res
    }
    #[allow(dead_code)]
    fn debug_tree(&self) {
        let mut que = std::collections::VecDeque::new();
        que.push_back(0);
        let mut cnt: usize = 0;
        while let Some(i) = que.pop_front() {
            print!("{:?} ", self.laz[i]);
            cnt += 1;
            if (cnt + 1).is_power_of_two() {
                print!("\n");
            }
            if i * 2 + 2 < self.laz.len() {
                que.push_back(i * 2 + 1);
                que.push_back(i * 2 + 2);
            }
        }
    }
}

fn main() {
    let stdin = std::io::stdin();
    let mut rd = ProconReader::new(stdin.lock());

    let n: usize = rd.get();
    let a: Vec<i64> = (0..n).map(|_| rd.get()).collect::<Vec<_>>();
    let inf = std::i64::MAX;
    let e = inf;
    let id = 0;
    let mut seg = LazySegmentTree::new(
        &a,
        e,
        |a, b| std::cmp::min(a, b),
        id,
        |f, g| f + g,
        |f, a| f + a,
    );
    let q: usize = rd.get();
    for _ in 0..q {
        let k: usize = rd.get();
        match k {
            1 => {
                let l: usize = rd.get();
                let r: usize = rd.get();
                let c: i64 = rd.get();
                seg.update((l - 1)..r, c);
            }
            2 => {
                let l: usize = rd.get();
                let r: usize = rd.get();
                let _: i64 = rd.get();
                println!("{}", seg.fold((l - 1)..r));
            }
            _ => {
                unreachable!();
            }
        }
    }
}