結果

問題 No.1234 典型RMQ
ユーザー くれちー
提出日時 2020-09-18 22:14:31
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 21,352 bytes
コンパイル時間 15,133 ms
コンパイル使用メモリ 379,620 KB
実行使用メモリ 6,144 KB
最終ジャッジ日時 2024-11-09 01:54:31
合計ジャッジ時間 18,707 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// The main code is at the very bottom.
#[allow(unused_imports)]
use {
  lib::byte::ByteChar,
  std::cell::{Cell, RefCell},
  std::cmp::{
    self,
    Ordering::{self, *},
    Reverse,
  },
  std::collections::*,
  std::convert::identity,
  std::fmt::{self, Debug, Display, Formatter},
  std::io::prelude::*,
  std::iter::{self, FromIterator},
  std::marker::PhantomData,
  std::mem,
  std::num::Wrapping,
  std::ops::{Range, RangeFrom, RangeInclusive, RangeTo, RangeToInclusive},
  std::process,
  std::rc::Rc,
  std::thread,
  std::time::{Duration, Instant},
  std::{char, f32, f64, i128, i16, i32, i64, i8, isize, str, u128, u16, u32, u64, u8, usize},
};
#[allow(unused_imports)]
#[macro_use]
pub mod lib {
  pub mod byte {
    pub use self::byte_char::*;
    mod byte_char {
      use std::error::Error;
      use std::fmt::{self, Debug, Display, Formatter};
      use std::str::FromStr;
      #[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
      #[repr(transparent)]
      pub struct ByteChar(pub u8);
      impl Debug for ByteChar {
        fn fmt(&self, f: &mut Formatter) -> fmt::Result {
          write!(f, "b'{}'", self.0 as char)
        }
      }
      impl Display for ByteChar {
        fn fmt(&self, f: &mut Formatter) -> fmt::Result {
          write!(f, "{}", self.0 as char)
        }
      }
      impl FromStr for ByteChar {
        type Err = ParseByteCharError;
        fn from_str(s: &str) -> Result<ByteChar, ParseByteCharError> {
          match s.as_bytes().len() {
            1 => Ok(ByteChar(s.as_bytes()[0])),
            0 => Err(ParseByteCharErrorKind::EmptyStr.into()),
            _ => Err(ParseByteCharErrorKind::TooManyBytes.into()),
          }
        }
      }
      #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
      pub struct ParseByteCharError {
        kind: ParseByteCharErrorKind,
      }
      impl Display for ParseByteCharError {
        fn fmt(&self, f: &mut Formatter) -> fmt::Result {
          f.write_str(match self.kind {
            ParseByteCharErrorKind::EmptyStr => "empty string",
            ParseByteCharErrorKind::TooManyBytes => "too many bytes",
          })
        }
      }
      impl Error for ParseByteCharError {}
      #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
      enum ParseByteCharErrorKind {
        EmptyStr,
        TooManyBytes,
      }
      impl From<ParseByteCharErrorKind> for ParseByteCharError {
        fn from(kind: ParseByteCharErrorKind) -> ParseByteCharError {
          ParseByteCharError { kind }
        }
      }
    }
  }
  pub mod io {
    pub use self::scanner::*;
    mod scanner {
      use std::io::{self, BufRead};
      use std::iter;
      use std::str::FromStr;
      #[derive(Debug)]
      pub struct Scanner<R> {
        reader: R,
        buf: String,
        pos: usize,
      }
      impl<R: BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
          Scanner {
            reader,
            buf: String::new(),
            pos: 0,
          }
        }
        pub fn next(&mut self) -> io::Result<&str> {
          let start = loop {
            match self.rest().find(|c| c != ' ') {
              Some(i) => break i,
              None => self.fill_buf()?,
            }
          };
          self.pos += start;
          let len = self.rest().find(' ').unwrap_or(self.rest().len());
          let s = &self.buf[self.pos..][..len]; // self.rest()[..len]
          self.pos += len;
          Ok(s)
        }
        pub fn parse_next<T>(&mut self) -> io::Result<Result<T, T::Err>>
        where
          T: FromStr,
        {
          Ok(self.next()?.parse())
        }
        pub fn parse_next_n<T>(&mut self, n: usize) -> io::Result<Result<Vec<T>, T::Err>>
        where
          T: FromStr,
        {
          iter::repeat_with(|| self.parse_next()).take(n).collect()
        }
        pub fn map_next_bytes<T, F>(&mut self, mut f: F) -> io::Result<Vec<T>>
        where
          F: FnMut(u8) -> T,
        {
          Ok(self.next()?.bytes().map(&mut f).collect())
        }
        pub fn map_next_bytes_n<T, F>(&mut self, n: usize, mut f: F) -> io::Result<Vec<Vec<T>>>
        where
          F: FnMut(u8) -> T,
        {
          iter::repeat_with(|| self.map_next_bytes(&mut f))
            .take(n)
            .collect()
        }
        fn rest(&self) -> &str {
          &self.buf[self.pos..]
        }
        fn fill_buf(&mut self) -> io::Result<()> {
          self.buf.clear();
          self.pos = 0;
          let read = self.reader.read_line(&mut self.buf)?;
          if read == 0 {
            return Err(io::ErrorKind::UnexpectedEof.into());
          }
          if *self.buf.as_bytes().last().unwrap() == b'\n' {
            self.buf.pop();
          }
          Ok(())
        }
      }
    }
  }
}
// https://github.com/rust-lang-ja/ac-library-rs/tree/ee0d3df1aa0e7d3c65daaa7cc9d7fb13a46928f2
#[allow(unused_imports)]
pub mod ac_library_rs {
  mod segtree {
    use crate::ac_library_rs::internal_type_traits::{BoundedAbove, BoundedBelow, One, Zero};
    use std::cmp::{max, min};
    use std::convert::Infallible;
    use std::marker::PhantomData;
    use std::ops::{Add, Mul};
    // TODO Should I split monoid-related traits to another module?
    pub trait Monoid {
      type S: Clone;
      fn identity() -> Self::S;
      fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
    }
    pub struct Max<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Max<S>
    where
      S: Copy + Ord + BoundedBelow,
    {
      type S = S;
      fn identity() -> Self::S {
        S::min_value()
      }
      fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        max(*a, *b)
      }
    }
    pub struct Min<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Min<S>
    where
      S: Copy + Ord + BoundedAbove,
    {
      type S = S;
      fn identity() -> Self::S {
        S::max_value()
      }
      fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        min(*a, *b)
      }
    }
    pub struct Additive<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Additive<S>
    where
      S: Copy + Add<Output = S> + Zero,
    {
      type S = S;
      fn identity() -> Self::S {
        S::zero()
      }
      fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a + *b
      }
    }
    pub struct Multiplicative<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Multiplicative<S>
    where
      S: Copy + Mul<Output = S> + One,
    {
      type S = S;
      fn identity() -> Self::S {
        S::one()
      }
      fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a * *b
      }
    }
  }
  mod lazysegtree {
    use crate::ac_library_rs::internal_bit::ceil_pow2;
    use crate::ac_library_rs::Monoid;
    pub trait MapMonoid {
      type M: Monoid;
      type F: Clone;
      // type S = <Self::M as Monoid>::S;
      fn identity_element() -> <Self::M as Monoid>::S {
        Self::M::identity()
      }
      fn binary_operation(
        a: &<Self::M as Monoid>::S,
        b: &<Self::M as Monoid>::S,
      ) -> <Self::M as Monoid>::S {
        Self::M::binary_operation(a, b)
      }
      fn identity_map() -> Self::F;
      fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S;
      fn composition(f: &Self::F, g: &Self::F) -> Self::F;
    }
    impl<F: MapMonoid> Default for LazySegtree<F> {
      fn default() -> Self {
        Self::new(0)
      }
    }
    impl<F: MapMonoid> LazySegtree<F> {
      pub fn new(n: usize) -> Self {
        vec![F::identity_element(); n].into()
      }
    }
    impl<F: MapMonoid> From<Vec<<F::M as Monoid>::S>> for LazySegtree<F> {
      fn from(v: Vec<<F::M as Monoid>::S>) -> Self {
        let n = v.len();
        let log = ceil_pow2(n as u32) as usize;
        let size = 1 << log;
        let mut d = vec![F::identity_element(); 2 * size];
        let lz = vec![F::identity_map(); size];
        d[size..(size + n)].clone_from_slice(&v);
        let mut ret = LazySegtree {
          n,
          size,
          log,
          d,
          lz,
        };
        for i in (1..size).rev() {
          ret.update(i);
        }
        ret
      }
    }
    impl<F: MapMonoid> LazySegtree<F> {
      pub fn set(&mut self, mut p: usize, x: <F::M as Monoid>::S) {
        assert!(p < self.n);
        p += self.size;
        for i in (1..=self.log).rev() {
          self.push(p >> i);
        }
        self.d[p] = x;
        for i in 1..=self.log {
          self.update(p >> i);
        }
      }
      pub fn get(&mut self, mut p: usize) -> <F::M as Monoid>::S {
        assert!(p < self.n);
        p += self.size;
        for i in (1..=self.log).rev() {
          self.push(p >> i);
        }
        self.d[p].clone()
      }
      pub fn prod(&mut self, mut l: usize, mut r: usize) -> <F::M as Monoid>::S {
        assert!(l <= r && r <= self.n);
        if l == r {
          return F::identity_element();
        }
        l += self.size;
        r += self.size;
        for i in (1..=self.log).rev() {
          if ((l >> i) << i) != l {
            self.push(l >> i);
          }
          if ((r >> i) << i) != r {
            self.push(r >> i);
          }
        }
        let mut sml = F::identity_element();
        let mut smr = F::identity_element();
        while l < r {
          if l & 1 != 0 {
            sml = F::binary_operation(&sml, &self.d[l]);
            l += 1;
          }
          if r & 1 != 0 {
            r -= 1;
            smr = F::binary_operation(&self.d[r], &smr);
          }
          l >>= 1;
          r >>= 1;
        }
        F::binary_operation(&sml, &smr)
      }
      pub fn all_prod(&self) -> <F::M as Monoid>::S {
        self.d[1].clone()
      }
      pub fn apply(&mut self, mut p: usize, f: F::F) {
        assert!(p < self.n);
        p += self.size;
        for i in (1..=self.log).rev() {
          self.push(p >> i);
        }
        self.d[p] = F::mapping(&f, &self.d[p]);
        for i in 1..=self.log {
          self.update(p >> i);
        }
      }
      pub fn apply_range(&mut self, mut l: usize, mut r: usize, f: F::F) {
        assert!(l <= r && r <= self.n);
        if l == r {
          return;
        }
        l += self.size;
        r += self.size;
        for i in (1..=self.log).rev() {
          if ((l >> i) << i) != l {
            self.push(l >> i);
          }
          if ((r >> i) << i) != r {
            self.push((r - 1) >> i);
          }
        }
        {
          let l2 = l;
          let r2 = r;
          while l < r {
            if l & 1 != 0 {
              self.all_apply(l, f.clone());
              l += 1;
            }
            if r & 1 != 0 {
              r -= 1;
              self.all_apply(r, f.clone());
            }
            l >>= 1;
            r >>= 1;
          }
          l = l2;
          r = r2;
        }
        for i in 1..=self.log {
          if ((l >> i) << i) != l {
            self.update(l >> i);
          }
          if ((r >> i) << i) != r {
            self.update((r - 1) >> i);
          }
        }
      }
      pub fn max_right<G>(&mut self, mut l: usize, g: G) -> usize
      where
        G: Fn(<F::M as Monoid>::S) -> bool,
      {
        assert!(l <= self.n);
        assert!(g(F::identity_element()));
        if l == self.n {
          return self.n;
        }
        l += self.size;
        for i in (1..=self.log).rev() {
          self.push(l >> i);
        }
        let mut sm = F::identity_element();
        while {
          // do
          while l % 2 == 0 {
            l >>= 1;
          }
          if !g(F::binary_operation(&sm, &self.d[l])) {
            while l < self.size {
              self.push(l);
              l *= 2;
              let res = F::binary_operation(&sm, &self.d[l]);
              if g(res.clone()) {
                sm = res;
                l += 1;
              }
            }
            return l - self.size;
          }
          sm = F::binary_operation(&sm, &self.d[l]);
          l += 1;
          //while
          {
            let l = l as isize;
            (l & -l) != l
          }
        } {}
        self.n
      }
      pub fn min_left<G>(&mut self, mut r: usize, g: G) -> usize
      where
        G: Fn(<F::M as Monoid>::S) -> bool,
      {
        assert!(r <= self.n);
        assert!(g(F::identity_element()));
        if r == 0 {
          return 0;
        }
        r += self.size;
        for i in (1..=self.log).rev() {
          self.push((r - 1) >> i);
        }
        let mut sm = F::identity_element();
        while {
          // do
          r -= 1;
          while r > 1 && r % 2 != 0 {
            r >>= 1;
          }
          if !g(F::binary_operation(&self.d[r], &sm)) {
            while r < self.size {
              self.push(r);
              r = 2 * r + 1;
              let res = F::binary_operation(&self.d[r], &sm);
              if g(res.clone()) {
                sm = res;
                r -= 1;
              }
            }
            return r + 1 - self.size;
          }
          sm = F::binary_operation(&self.d[r], &sm);
          // while
          {
            let r = r as isize;
            (r & -r) != r
          }
        } {}
        0
      }
    }
    pub struct LazySegtree<F>
    where
      F: MapMonoid,
    {
      n: usize,
      size: usize,
      log: usize,
      d: Vec<<F::M as Monoid>::S>,
      lz: Vec<F::F>,
    }
    impl<F> LazySegtree<F>
    where
      F: MapMonoid,
    {
      fn update(&mut self, k: usize) {
        self.d[k] = F::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]);
      }
      fn all_apply(&mut self, k: usize, f: F::F) {
        self.d[k] = F::mapping(&f, &self.d[k]);
        if k < self.size {
          self.lz[k] = F::composition(&f, &self.lz[k]);
        }
      }
      fn push(&mut self, k: usize) {
        self.all_apply(2 * k, self.lz[k].clone());
        self.all_apply(2 * k + 1, self.lz[k].clone());
        self.lz[k] = F::identity_map();
      }
    }
    // TODO is it useful?
    use std::fmt::{Debug, Error, Formatter, Write};
    impl<F> Debug for LazySegtree<F>
    where
      F: MapMonoid,
      F::F: Debug,
      <F::M as Monoid>::S: Debug,
    {
      fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        for i in 0..self.log {
          for j in 0..1 << i {
            f.write_fmt(format_args!(
              "{:?}[{:?}]\t",
              self.d[(1 << i) + j],
              self.lz[(1 << i) + j]
            ))?;
          }
          f.write_char('\n')?;
        }
        for i in 0..self.size {
          f.write_fmt(format_args!("{:?}\t", self.d[self.size + i]))?;
        }
        Ok(())
      }
    }
  }
  pub(crate) mod internal_bit {
    // Skipped:
    //
    // - `bsf` = `__builtin_ctz`: is equivalent to `{integer}::trailing_zeros`
    #[allow(dead_code)]
    pub(crate) fn ceil_pow2(n: u32) -> u32 {
      32 - n.saturating_sub(1).leading_zeros()
    }
  }
  pub(crate) mod internal_type_traits {
    use std::{
      fmt,
      iter::{Product, Sum},
      ops::{
        Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div,
        DivAssign, Mul, MulAssign, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
        SubAssign,
      },
    };
    // Skipped:
    //
    // - `is_signed_int_t<T>`   (probably won't be used directly in `modint.rs`)
    // - `is_unsigned_int_t<T>` (probably won't be used directly in `modint.rs`)
    // - `to_unsigned_t<T>`     (not used in `fenwicktree.rs`)
    /// Corresponds to `std::is_integral` in C++.
    // We will remove unnecessary bounds later.
    //
    // Maybe we should rename this to `PrimitiveInteger` or something, as it probably won't be used in the
    // same way as the original ACL.
    pub trait Integral:
      'static
      + Send
      + Sync
      + Copy
      + Ord
      + Not<Output = Self>
      + Add<Output = Self>
      + Sub<Output = Self>
      + Mul<Output = Self>
      + Div<Output = Self>
      + Rem<Output = Self>
      + AddAssign
      + SubAssign
      + MulAssign
      + DivAssign
      + RemAssign
      + Sum
      + Product
      + BitOr<Output = Self>
      + BitAnd<Output = Self>
      + BitXor<Output = Self>
      + BitOrAssign
      + BitAndAssign
      + BitXorAssign
      + Shl<Output = Self>
      + Shr<Output = Self>
      + ShlAssign
      + ShrAssign
      + fmt::Display
      + fmt::Debug
      + fmt::Binary
      + fmt::Octal
      + Zero
      + One
      + BoundedBelow
      + BoundedAbove
    {
    }
    /// Class that has additive identity element
    pub trait Zero {
      /// The additive identity element
      fn zero() -> Self;
    }
    /// Class that has multiplicative identity element
    pub trait One {
      /// The multiplicative identity element
      fn one() -> Self;
    }
    pub trait BoundedBelow {
      fn min_value() -> Self;
    }
    pub trait BoundedAbove {
      fn max_value() -> Self;
    }
    macro_rules! impl_integral {
      ($($ty:ty),*) => {
        $(
          impl Zero for $ty {
            #[inline]
            fn zero() -> Self {
              0
            }
          }
          impl One for $ty {
            #[inline]
            fn one() -> Self {
              1
            }
          }
          impl BoundedBelow for $ty {
            #[inline]
            fn min_value() -> Self {
              Self::min_value()
            }
          }
          impl BoundedAbove for $ty {
            #[inline]
            fn max_value() -> Self {
              Self::max_value()
            }
          }
          impl Integral for $ty {}
        )*
      };
    }
    impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
  }
  pub use lazysegtree::{LazySegtree, MapMonoid};
  pub use segtree::{Additive, Max, Min, Monoid, Multiplicative};
}
#[allow(unused_macros)]
macro_rules! eprint {
  ($($arg:tt)*) => {
    if cfg!(debug_assertions) {
      std::eprint!($($arg)*)
    }
  };
}
#[allow(unused_macros)]
macro_rules! eprintln {
  ($($arg:tt)*) => {
    if cfg!(debug_assertions) {
      std::eprintln!($($arg)*)
    }
  };
}
#[allow(unused_macros)]
macro_rules! dbg {
  ($($arg:tt)*) => {
    if cfg!(debug_assertions) {
      std::dbg!($($arg)*)
    } else {
      ($($arg)*)
    }
  };
}
const CUSTOM_STACK_SIZE_MIB: Option<usize> = Some(1024);
const INTERACTIVE: bool = false;
fn main() -> std::io::Result<()> {
  match CUSTOM_STACK_SIZE_MIB {
    Some(stack_size_mib) => std::thread::Builder::new()
      .name("run_solver".to_owned())
      .stack_size(stack_size_mib * 1024 * 1024)
      .spawn(run_solver)?
      .join()
      .unwrap(),
    None => run_solver(),
  }
}
fn run_solver() -> std::io::Result<()> {
  let stdin = std::io::stdin();
  let reader = stdin.lock();
  let stdout = std::io::stdout();
  let writer = stdout.lock();
  macro_rules! with_wrapper {
    ($($wrapper:expr)?) => {{
      let mut writer = $($wrapper)?(writer);
      solve(reader, &mut writer)?;
      writer.flush()
    }};
  }
  if cfg!(debug_assertions) || INTERACTIVE {
    with_wrapper!()
  } else {
    with_wrapper!(std::io::BufWriter::new)
  }
}
fn solve<R, W>(reader: R, mut writer: W) -> std::io::Result<()>
where
  R: BufRead,
  W: Write,
{
  let mut _scanner = lib::io::Scanner::new(reader);
  #[allow(unused_macros)]
  macro_rules! scan {
    ($T:ty) => {
      _scanner.parse_next::<$T>()?.unwrap()
    };
    ($($T:ty),+) => {
      ($(scan!($T)),+)
    };
    ($T:ty; $n:expr) => {
      _scanner.parse_next_n::<$T>($n)?.unwrap()
    };
    ($($T:ty),+; $n:expr) => {
      iter::repeat_with(|| -> std::io::Result<_> { Ok(($(scan!($T)),+)) })
        .take($n)
        .collect::<std::io::Result<Vec<_>>>()?
    };
  }
  #[allow(unused_macros)]
  macro_rules! scan_bytes_map {
    ($f:expr) => {
      _scanner.map_next_bytes($f)?
    };
    ($f:expr; $n:expr) => {
      _scanner.map_next_bytes_n($n, $f)?
    };
  }
  #[allow(unused_macros)]
  macro_rules! print {
    ($($arg:tt)*) => {
      write!(writer, $($arg)*)?
    };
  }
  #[allow(unused_macros)]
  macro_rules! println {
    ($($arg:tt)*) => {
      writeln!(writer, $($arg)*)?
    };
  }
  #[allow(unused_macros)]
  macro_rules! answer {
    ($($arg:tt)*) => {{
      println!($($arg)*);
      return Ok(());
    }};
  }
  {
    use ac_library_rs::{LazySegtree, MapMonoid, Min, Monoid as _};
    enum F {}
    impl MapMonoid for F {
      type M = Min<i64>;
      type F = i64;
      fn identity_map() -> Self::F {
        0
      }
      fn mapping(&f: &i64, &a: &i64) -> i64 {
        if a == Min::<i64>::identity() {
          a
        } else {
          f + a
        }
      }
      fn composition(&f: &i64, &g: &i64) -> i64 {
        f + g
      }
    }
    let n = scan!(usize);
    let a = scan!(i64; n);
    let mut segtree = LazySegtree::<F>::from(a);
    let q = scan!(usize);
    for _ in 0..q {
      let (k, l, r, c) = scan!(u8, usize, usize, i64);
      match k {
        1 => segtree.apply_range(l - 1, r, c),
        2 => {
          let ans = segtree.prod(l - 1, r);
          println!("{}", ans);
        }
        _ => unreachable!(),
      }
    }
  }
  #[allow(unreachable_code)]
  Ok(())
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0