use std::io::{stdout, BufWriter, Write}; struct MinAdd; struct MinWithCount; impl Monoid for MinWithCount { type S = (i64, i64); fn identity() -> Self::S { (1, 9999999999999) } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { (a.0 + b.0, std::cmp::min(a.1, b.1)) } } impl MapMonoid for MinAdd { type M = MinWithCount; type F = i64; fn identity_map() -> Self::F { 0 } fn mapping(f: &Self::F, x: &::S) -> ::S { (x.0, x.1 + f) } fn composition(f: &Self::F, g: &Self::F) -> Self::F { *f + *g } } fn main() { let out = stdout(); let mut out = BufWriter::new(out.lock()); inputv! { n:usize } let a = input_vector::(); let mut segtree: LazySegtree = LazySegtree::new(n); for (i, &x) in a.iter().enumerate() { segtree.set(i, (1, x)); } inputv! { q:usize } for _ in 0..q { inputv! { k:usize,l:usize,r:usize,c:i64 } if k == 1 { segtree.apply_range(l - 1, r, c); } else { writeln!(out, "{}", segtree.prod(l - 1, r).1).unwrap(); } } } //https://github.com/rust-lang-ja/ac-library-rs //https://github.com/manta1130/competitive-template-rs use input::*; use lazysegtree::*; use segtree::*; pub mod input { use std::cell::RefCell; use std::io; pub const SPLIT_DELIMITER: char = ' '; pub use std::io::prelude::*; #[macro_export] thread_local! { pub static INPUT_BUFFER:RefCell>=RefCell::new(std::collections::VecDeque::new()); } #[macro_export] macro_rules! input_internal { ($x:ident : $t:ty) => { INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { let temp_str = input_line_str(); let mut split_result_iter = temp_str .split(SPLIT_DELIMITER) .map(|q| q.to_string()) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); let mut buf_split_result = String::new(); INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap()); let $x: $t = buf_split_result.parse().unwrap(); }; (mut $x:ident : $t:ty) => { INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { let temp_str = input_line_str(); let mut split_result_iter = temp_str .split(SPLIT_DELIMITER) .map(|q| q.to_string()) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); let mut buf_split_result = String::new(); INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap()); let mut $x: $t = buf_split_result.parse().unwrap(); }; } #[macro_export] macro_rules! inputv { ($i:ident : $t:ty) => { input_internal!{$i : $t} }; (mut $i:ident : $t:ty) => { input_internal!{mut $i : $t} }; ($i:ident : $t:ty $(,)*) => { input_internal!{$i : $t} }; (mut $i:ident : $t:ty $(,)*) => { input_internal!{mut $i : $t} }; (mut $i:ident : $t:ty,$($q:tt)*) => { input_internal!{mut $i : $t} inputv!{$($q)*} }; ($i:ident : $t:ty,$($q:tt)*) => { input_internal!{$i : $t} inputv!{$($q)*} }; } pub fn input_all() { INPUT_BUFFER.with(|p| { if p.borrow().len() == 0 { let mut temp_str = String::new(); std::io::stdin().read_to_string(&mut temp_str).unwrap(); let mut split_result_iter = temp_str .split_whitespace() .map(|q| q.to_string()) .collect::>(); p.borrow_mut().append(&mut split_result_iter) } }); } pub fn input_line_str() -> String { let mut s = String::new(); io::stdin().read_line(&mut s).unwrap(); s.trim().to_string() } #[allow(clippy::match_wild_err_arm)] pub fn input_vector() -> Vec where T: std::str::FromStr, { let mut v: Vec = Vec::new(); let s = input_line_str(); let split_result = s.split(SPLIT_DELIMITER); for z in split_result { let buf = match z.parse() { Ok(r) => r, Err(_) => panic!("Parse Error",), }; v.push(buf); } v } #[allow(clippy::match_wild_err_arm)] pub fn input_vector_row(n: usize) -> Vec where T: std::str::FromStr, { let mut v = Vec::with_capacity(n); for _ in 0..n { let buf = match input_line_str().parse() { Ok(r) => r, Err(_) => panic!("Parse Error",), }; v.push(buf); } v } pub trait ToCharVec { fn to_charvec(&self) -> Vec; } impl ToCharVec for String { fn to_charvec(&self) -> Vec { self.to_string().chars().collect::>() } } } pub mod internal_bit { #[allow(dead_code)] pub(crate) fn ceil_pow2(n: u32) -> u32 { 32 - n.saturating_sub(1).leading_zeros() } } pub 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, }, }; pub trait Integral: 'static + Send + Sync + Copy + Ord + Not + Add + Sub + Mul + Div + Rem + AddAssign + SubAssign + MulAssign + DivAssign + RemAssign + Sum + Product + BitOr + BitAnd + BitXor + BitOrAssign + BitAndAssign + BitXorAssign + Shl + Shr + ShlAssign + ShrAssign + fmt::Display + fmt::Debug + fmt::Binary + fmt::Octal + Zero + One + BoundedBelow + BoundedAbove { } pub trait Zero { fn zero() -> Self; } pub trait One { 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 mod lazysegtree { use crate::internal_bit::ceil_pow2; use crate::Monoid; pub trait MapMonoid { type M: Monoid; type F: Clone; fn identity_element() -> ::S { Self::M::identity() } fn binary_operation( a: &::S, b: &::S, ) -> ::S { Self::M::binary_operation(a, b) } fn identity_map() -> Self::F; fn mapping(f: &Self::F, x: &::S) -> ::S; fn composition(f: &Self::F, g: &Self::F) -> Self::F; } impl Default for LazySegtree { fn default() -> Self { Self::new(0) } } impl LazySegtree { pub fn new(n: usize) -> Self { vec![F::identity_element(); n].into() } } impl From::S>> for LazySegtree { fn from(v: Vec<::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 LazySegtree { pub fn set(&mut self, mut p: usize, x: ::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) -> ::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) -> ::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) -> ::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(&mut self, mut l: usize, g: G) -> usize where G: Fn(::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 { 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; { let l = l as isize; (l & -l) != l } } {} self.n } pub fn min_left(&mut self, mut r: usize, g: G) -> usize where G: Fn(::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 { 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); { let r = r as isize; (r & -r) != r } } {} 0 } } pub struct LazySegtree where F: MapMonoid, { n: usize, size: usize, log: usize, d: Vec<::S>, lz: Vec, } impl LazySegtree 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(); } } use std::fmt::{Debug, Error, Formatter, Write}; impl Debug for LazySegtree where F: MapMonoid, F::F: Debug, ::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 mod segtree { use crate::internal_bit::ceil_pow2; use crate::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}; pub trait Monoid { type S: Clone; fn identity() -> Self::S; fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S; } pub struct Max(Infallible, PhantomData S>); impl Monoid for Max 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(Infallible, PhantomData S>); impl Monoid for Min 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(Infallible, PhantomData S>); impl Monoid for Additive where S: Copy + Add + 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(Infallible, PhantomData S>); impl Monoid for Multiplicative where S: Copy + Mul + One, { type S = S; fn identity() -> Self::S { S::one() } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { *a * *b } } impl Default for Segtree { fn default() -> Self { Segtree::new(0) } } impl Segtree { pub fn new(n: usize) -> Segtree { vec![M::identity(); n].into() } } impl From> for Segtree { fn from(v: Vec) -> Self { let n = v.len(); let log = ceil_pow2(n as u32) as usize; let size = 1 << log; let mut d = vec![M::identity(); 2 * size]; d[size..(size + n)].clone_from_slice(&v); let mut ret = Segtree { n, size, log, d }; for i in (1..size).rev() { ret.update(i); } ret } } impl Segtree { pub fn set(&mut self, mut p: usize, x: M::S) { assert!(p < self.n); p += self.size; self.d[p] = x; for i in 1..=self.log { self.update(p >> i); } } pub fn get(&self, p: usize) -> M::S { assert!(p < self.n); self.d[p + self.size].clone() } pub fn prod(&self, mut l: usize, mut r: usize) -> M::S { assert!(l <= r && r <= self.n); let mut sml = M::identity(); let mut smr = M::identity(); l += self.size; r += self.size; while l < r { if l & 1 != 0 { sml = M::binary_operation(&sml, &self.d[l]); l += 1; } if r & 1 != 0 { r -= 1; smr = M::binary_operation(&self.d[r], &smr); } l >>= 1; r >>= 1; } M::binary_operation(&sml, &smr) } pub fn all_prod(&self) -> M::S { self.d[1].clone() } pub fn max_right(&self, mut l: usize, f: F) -> usize where F: Fn(&M::S) -> bool, { assert!(l <= self.n); assert!(f(&M::identity())); if l == self.n { return self.n; } l += self.size; let mut sm = M::identity(); while { while l % 2 == 0 { l >>= 1; } if !f(&M::binary_operation(&sm, &self.d[l])) { while l < self.size { l *= 2; let res = M::binary_operation(&sm, &self.d[l]); if f(&res) { sm = res; l += 1; } } return l - self.size; } sm = M::binary_operation(&sm, &self.d[l]); l += 1; { let l = l as isize; (l & -l) != l } } {} self.n } pub fn min_left(&self, mut r: usize, f: F) -> usize where F: Fn(&M::S) -> bool, { assert!(r <= self.n); assert!(f(&M::identity())); if r == 0 { return 0; } r += self.size; let mut sm = M::identity(); while { r -= 1; while r > 1 && r % 2 == 1 { r >>= 1; } if !f(&M::binary_operation(&self.d[r], &sm)) { while r < self.size { r = 2 * r + 1; let res = M::binary_operation(&self.d[r], &sm); if f(&res) { sm = res; r -= 1; } } return r + 1 - self.size; } sm = M::binary_operation(&self.d[r], &sm); { let r = r as isize; (r & -r) != r } } {} 0 } fn update(&mut self, k: usize) { self.d[k] = M::binary_operation(&self.d[2 * k], &self.d[2 * k + 1]); } } pub struct Segtree where M: Monoid, { n: usize, size: usize, log: usize, d: Vec, } }