#634838 (Rust) No.1441 MErGe

• 問題: No.1441 MErGe
• ユーザー: RheoTommy
• 提出日時: 2021-03-26 23:04:33
• 言語: Rust (1.83.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 9,778 bytes
• コンパイル時間: 15,078 ms
• コンパイル使用メモリ: 386,092 KB
• 実行使用メモリ: 33,748 KB
• 最終ジャッジ日時: 2024-11-29 01:13:31
• 合計ジャッジ時間: 49,258 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 1 WA * 10 TLE * 17

ソースコード

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

// # ファイル構成
// - use宣言
// - libモジュール
// - main関数
// - basicモジュール
//
// 常に使うテンプレートライブラリはbasicモジュール内にあります。
// 問題に応じて使うライブラリlibモジュール内にコピペしています。
// ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder
// Twitterはこちら → https://twitter.com/RheoTommy

use std::collections::*;
use std::io::{stdout, BufWriter, Write};

use crate::basic::*;
use crate::lib::*;

pub mod lib {
    /// 遅延セグ木にのせるMonoid
    pub trait Monoid {
        type Item: std::fmt::Debug + Clone;
        /// 単位元
        fn id() -> Self::Item;
        /// 二項演算
        fn op(a: &Self::Item, b: &Self::Item) -> Self::Item;
    }

    pub struct LazySegTree<M: Monoid, L: Monoid> {
        data: Vec<M::Item>,
        lazy: Vec<Option<L::Item>>,
        n: usize,
    }

    impl<M: Monoid, L: Monoid> std::fmt::Debug for LazySegTree<M, L> {
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
            let v = &self.data[self.n - 1..];
            write!(f, "{:?}", v)
        }
    }

    impl<M: Monoid, L: Monoid> LazySegTree<M, L> {
        /// すべて単位元で埋めた長さnの遅延セグ木の生成
        pub fn new(n: usize) -> Self {
            let mut i = 1;
            while i < n {
                i *= 2;
            }
            let data = (0..2 * i - 1).map(|_| M::id()).collect::<Vec<_>>();
            Self {
                data,
                lazy: vec![None; 2 * i - 1],
                n: i,
            }
        }
        /// O(n)でスライスからセグ木を生成
        pub fn from_slice(slice: &[M::Item]) -> Self {
            let mut i = 1;
            while i < slice.len() {
                i *= 2;
            }
            let mut data = vec![M::id(); 2 * i - 1];
            for j in 0..slice.len() {
                data[j + i - 1] = slice[j].clone();
            }
            if slice.len() != 1 {
                for j in (0..=(i - 2)).rev() {
                    data[j] = M::op(&data[j * 2 + 1], &data[j * 2 + 2]);
                }
            }
            Self {
                data,
                lazy: vec![None; 2 * i - 1],
                n: i,
            }
        }
        /// そのノードの持つ区間の一番左のIndex
        fn start_of_section(&self, mut k: usize) -> usize {
            while k < self.n - 1 {
                k = k * 2 + 1;
            }
            k
        }
        /// そのノードの持つ区間の長さ
        fn len_of_section(&self, mut k: usize) -> usize {
            let mut j = k;
            while k < self.n - 1 {
                k = k * 2 + 1;
                j = j * 2 + 2;
            }
            j - k + 1
        }
        /// 遅延を評価し子ノードに伝播
        fn eval(
            &mut self,
            k: usize,
            apply: &mut impl FnMut(&M::Item, &L::Item, usize, usize) -> M::Item,
        ) {
            if let Some(lv) = self.lazy[k].clone() {
                if k < self.n - 1 {
                    self.lazy[k * 2 + 1] = if let Some(p) = &self.lazy[k * 2 + 1] {
                        Some(L::op(&lv, p))
                    } else {
                        Some(lv.clone())
                    };
                    self.lazy[k * 2 + 2] = if let Some(p) = &self.lazy[k * 2 + 2] {
                        Some(L::op(&lv, &p))
                    } else {
                        Some(lv.clone())
                    };
                }
                self.data[k] = apply(
                    &self.data[k],
                    &lv,
                    self.start_of_section(k) + 1 - self.n,
                    self.len_of_section(k),
                );
                self.lazy[k] = None;
            }
        }
        fn fold_sub(
            &mut self,
            start: usize,
            end: usize,
            k: usize,
            l: usize,
            r: usize,
            apply: &mut impl FnMut(&M::Item, &L::Item, usize, usize) -> M::Item,
        ) -> M::Item {
            self.eval(k, apply);
            if end <= l || r <= start {
                M::id()
            } else if start <= l && r <= end {
                self.data[k].clone()
            } else {
                let vl = &self.fold_sub(start, end, k * 2 + 1, l, (l + r) / 2, apply);
                let vr = &self.fold_sub(start, end, k * 2 + 2, (l + r) / 2, r, apply);
                M::op(vl, vr)
            }
        }
        pub fn fold(
            &mut self,
            start: usize,
            end: usize,
            apply: &mut impl FnMut(&M::Item, &L::Item, usize, usize) -> M::Item,
        ) -> M::Item {
            self.fold_sub(start, end, 0, 0, self.n, apply)
        }
        pub fn set_section(
            &mut self,
            start: usize,
            end: usize,
            lv: L::Item,
            apply: &mut impl FnMut(&M::Item, &L::Item, usize, usize) -> M::Item,
        ) {
            self.set_section_sub(start, end, 0, 0, self.n, lv, apply)
        }
        fn set_section_sub(
            &mut self,
            start: usize,
            end: usize,
            k: usize,
            l: usize,
            r: usize,
            lv: L::Item,
            apply: &mut impl FnMut(&M::Item, &L::Item, usize, usize) -> M::Item,
        ) {
            self.eval(k, apply);
            if start <= l && r <= end {
                self.lazy[k] = Some(lv.clone());
                self.eval(k, apply);
            } else if start < r && l < end {
                self.set_section_sub(start, end, k * 2 + 1, l, (l + r) / 2, lv.clone(), apply);
                self.set_section_sub(start, end, k * 2 + 2, (l + r) / 2, r, lv.clone(), apply);
                self.data[k] = M::op(&self.data[k * 2 + 1], &self.data[k * 2 + 2]);
            }
        }
    }
}

struct Sum;
impl Monoid for Sum {
    type Item = usize;

    fn id() -> Self::Item {
        0
    }

    fn op(a: &Self::Item, b: &Self::Item) -> Self::Item {
        a + b
    }
}

struct Update;
impl Monoid for Update {
    type Item = usize;
    fn id() -> usize {
        0
    }
    fn op(_a: &usize, b: &usize) -> usize {
        *b
    }
}

fn main() {
    let out = stdout();
    let mut writer = BufWriter::new(out.lock());
    let mut sc = Scanner::new();

    let n = sc.next_usize();
    let q = sc.next_usize();
    let mut st = LazySegTree::<Sum, Update>::new(n);
    let apply = &mut |_v: &usize, lv: &usize, _ind: usize, len: usize| *lv * len;

    let mut a = (0..n).map(|_| sc.next_int()).collect::<Vec<_>>();
    a.insert(0, 0);
    let mut cum_sum = a.clone();
    for i in 0..n {
        cum_sum[i + 1] += cum_sum[i];
    }
    st.set_section(0, n, 1, apply);

    for _ in 0..q {
        let t = sc.next_usize();
        let l = sc.next_usize() - 1;
        let r = sc.next_usize();
        let ll = index(l, &mut st, apply, n);
        let rr = index(r, &mut st, apply, n);
        // writeln!(writer, "{:?}", (ll, rr));
        if t == 1 {
            st.set_section(ll + 1, rr, 0, apply);
        } else {
            writeln!(writer, "{}", cum_sum[rr] - cum_sum[ll]).unwrap();
        }
    }
}

fn index(
    i: usize,
    st: &mut LazySegTree<Sum, Update>,
    apply: &mut impl Fn(&usize, &usize, usize, usize) -> usize,
    n: usize,
) -> usize {
    let mut l = -1;
    let mut r = n as isize;
    while r - l > 1 {
        let mid = (l + r) as usize / 2;
        if st.fold(0, mid, apply) >= i {
            r = mid as isize;
        } else {
            l = mid as isize;
        }
    }
    r as usize
}

pub mod basic {
    pub const U_INF: u64 = (1 << 60) + (1 << 30);
    pub const I_INF: i64 = (1 << 60) + (1 << 30);

    pub struct Scanner {
        buf: std::collections::VecDeque<String>,
        reader: std::io::BufReader<std::io::Stdin>,
    }

    impl Scanner {
        pub fn new() -> Self {
            Self {
                buf: std::collections::VecDeque::new(),
                reader: std::io::BufReader::new(std::io::stdin()),
            }
        }

        fn scan_line(&mut self) {
            use std::io::BufRead;
            let mut flag = 0;
            while self.buf.is_empty() {
                let mut s = String::new();
                self.reader.read_line(&mut s).unwrap();
                let mut iter = s.split_whitespace().peekable();
                if iter.peek().is_none() {
                    if flag >= 5 {
                        panic!("There is no input!");
                    }
                    flag += 1;
                    continue;
                }

                for si in iter {
                    self.buf.push_back(si.to_string());
                }
            }
        }

        pub fn next<T: std::str::FromStr>(&mut self) -> T {
            self.scan_line();
            self.buf
                .pop_front()
                .unwrap()
                .parse()
                .unwrap_or_else(|_| panic!("Couldn't parse!"))
        }

        pub fn next_usize(&mut self) -> usize {
            self.next()
        }

        pub fn next_int(&mut self) -> i64 {
            self.next()
        }

        pub fn next_uint(&mut self) -> u64 {
            self.next()
        }

        pub fn next_chars(&mut self) -> Vec<char> {
            self.next::<String>().chars().collect()
        }

        pub fn next_string(&mut self) -> String {
            self.next()
        }

        pub fn next_char(&mut self) -> char {
            self.next()
        }

        pub fn next_float(&mut self) -> f64 {
            self.next()
        }
    }
}