fn main() { input! { n: usize, a: [usize; n], } let mut ans = M::zero(); let mut seg = SegmentTreePURQ::new(n, 0, |a, b| std::cmp::max(*a, *b)); for (i, a) in a.iter().enumerate() { seg.update_tmp(i, *a); } seg.update_all(); let mut dfs = vec![(0, n)]; while let Some((l, r)) = dfs.pop() { if l >= r { continue; } let v = seg.find(l, r); let x = seg.max_right(l, |p| *p < v); ans += M::from(x - l + 1) * M::from(r - x) * M::from(v).pow(2); dfs.push((l, x)); dfs.push((x + 1, r)); } let mut seg = SegmentTreePURQ::new(n, std::usize::MAX, |a, b| std::cmp::min(*a, *b)); for (i, a) in a.iter().enumerate() { seg.update_tmp(i, *a); } seg.update_all(); let mut dfs = vec![(0, n)]; while let Some((l, r)) = dfs.pop() { if l >= r { continue; } let v = seg.find(l, r); let x = seg.max_right(l, |p| *p > v); ans += M::from(x - l + 1) * M::from(r - x) * M::from(v).pow(2); dfs.push((l, x)); dfs.push((x + 1, r)); } let mut max: Vec<(usize, usize)> = vec![]; let mut min: Vec<(usize, usize)> = vec![]; let mut seg = LazySegmentTree::new(n, R); for (i, &a) in a.iter().enumerate() { let mut x = i; while max.last().map_or(false, |p| p.0 < a) { let (v, l) = max.pop().unwrap(); seg.update(l, x, [M::zero(), M::from(a - v)]); x = l; } max.push((a, x)); let mut x = i; while min.last().map_or(false, |p| p.0 > a) { let (v, l) = min.pop().unwrap(); seg.update(l, x, [-M::from(v - a), M::zero()]); x = l; } min.push((a, x)); seg.set_at(i, [M::one(), M::from(a), M::from(a), M::from(a * a)]); ans += seg.find(0, n)[3] * -M::new(2); } println!("{}", ans); } type M = ModInt<998244353>; struct R; impl TE for R { type T = [M; 4]; type E = [M; 2]; fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T { let mut res = [M::zero(); 4]; for i in 0..4 { res[i] = l[i] + r[i]; } res } fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T { let mut x = *x; for (i, f) in f.iter().enumerate() { for x in x.chunks_exact_mut(2 << i) { let (l, r) = x.split_at_mut(1 << i); for (r, l) in r.iter_mut().zip(l.iter()) { *r += *l * *f; } } } x } fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E { [g[0] + h[0], g[1] + h[1]] } fn e(&self) -> Self::T { [M::zero(); 4] } fn id(&self) -> Self::E { [M::zero(); 2] } } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // ---------- begin modint ---------- pub const fn pow_mod(mut r: u32, mut n: u32, m: u32) -> u32 { let mut t = 1; while n > 0 { if n & 1 == 1 { t = (t as u64 * r as u64 % m as u64) as u32; } r = (r as u64 * r as u64 % m as u64) as u32; n >>= 1; } t } pub const fn primitive_root(p: u32) -> u32 { let mut m = p - 1; let mut f = [1; 30]; let mut k = 0; let mut d = 2; while d * d <= m { if m % d == 0 { f[k] = d; k += 1; } while m % d == 0 { m /= d; } d += 1; } if m > 1 { f[k] = m; k += 1; } let mut g = 1; while g < p { let mut ok = true; let mut i = 0; while i < k { ok &= pow_mod(g, (p - 1) / f[i], p) > 1; i += 1; } if ok { break; } g += 1; } g } pub const fn is_prime(n: u32) -> bool { if n <= 1 { return false; } let mut d = 2; while d * d <= n { if n % d == 0 { return false; } d += 1; } true } #[derive(Clone, Copy, PartialEq, Eq)] pub struct ModInt(u32); impl ModInt<{ M }> { const REM: u32 = { let mut t = 1u32; let mut s = !M + 1; let mut n = !0u32 >> 2; while n > 0 { if n & 1 == 1 { t = t.wrapping_mul(s); } s = s.wrapping_mul(s); n >>= 1; } t }; const INI: u64 = ((1u128 << 64) % M as u128) as u64; const IS_PRIME: () = assert!(is_prime(M)); const PRIMITIVE_ROOT: u32 = primitive_root(M); const ORDER: usize = 1 << (M - 1).trailing_zeros(); const fn reduce(x: u64) -> u32 { let _ = Self::IS_PRIME; let b = (x as u32 * Self::REM) as u64; let t = x + b * M as u64; let mut c = (t >> 32) as u32; if c >= M { c -= M; } c as u32 } const fn multiply(a: u32, b: u32) -> u32 { Self::reduce(a as u64 * b as u64) } pub const fn new(v: u32) -> Self { assert!(v < M); Self(Self::reduce(v as u64 * Self::INI)) } pub const fn const_mul(&self, rhs: Self) -> Self { Self(Self::multiply(self.0, rhs.0)) } pub const fn pow(&self, mut n: u64) -> Self { let mut t = Self::new(1); let mut r = *self; while n > 0 { if n & 1 == 1 { t = t.const_mul(r); } r = r.const_mul(r); n >>= 1; } t } pub const fn inv(&self) -> Self { assert!(self.0 != 0); self.pow(M as u64 - 2) } pub const fn get(&self) -> u32 { Self::reduce(self.0 as u64) } pub const fn zero() -> Self { Self::new(0) } pub const fn one() -> Self { Self::new(1) } } impl Add for ModInt<{ M }> { type Output = Self; fn add(self, rhs: Self) -> Self::Output { let mut v = self.0 + rhs.0; if v >= M { v -= M; } Self(v) } } impl Sub for ModInt<{ M }> { type Output = Self; fn sub(self, rhs: Self) -> Self::Output { let mut v = self.0 - rhs.0; if self.0 < rhs.0 { v += M; } Self(v) } } impl Mul for ModInt<{ M }> { type Output = Self; fn mul(self, rhs: Self) -> Self::Output { self.const_mul(rhs) } } impl Div for ModInt<{ M }> { type Output = Self; fn div(self, rhs: Self) -> Self::Output { self * rhs.inv() } } impl AddAssign for ModInt<{ M }> { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl SubAssign for ModInt<{ M }> { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl MulAssign for ModInt<{ M }> { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl DivAssign for ModInt<{ M }> { fn div_assign(&mut self, rhs: Self) { *self = *self / rhs; } } impl Neg for ModInt<{ M }> { type Output = Self; fn neg(self) -> Self::Output { if self.0 == 0 { self } else { Self(M - self.0) } } } impl std::fmt::Display for ModInt<{ M }> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl std::fmt::Debug for ModInt<{ M }> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.get()) } } impl std::str::FromStr for ModInt<{ M }> { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result { let val = s.parse::()?; Ok(ModInt::new(val)) } } impl From for ModInt<{ M }> { fn from(val: usize) -> ModInt<{ M }> { ModInt::new((val % M as usize) as u32) } } // ---------- end modint ---------- // ---------- begin precalc ---------- pub struct Precalc { fact: Vec>, ifact: Vec>, inv: Vec>, } impl Precalc { pub fn new(size: usize) -> Self { let mut fact = vec![ModInt::one(); size + 1]; let mut ifact = vec![ModInt::one(); size + 1]; let mut inv = vec![ModInt::one(); size + 1]; for i in 2..=size { fact[i] = fact[i - 1] * ModInt::from(i); } ifact[size] = fact[size].inv(); for i in (2..=size).rev() { inv[i] = ifact[i] * fact[i - 1]; ifact[i - 1] = ifact[i] * ModInt::from(i); } Self { fact, ifact, inv } } pub fn fact(&self, n: usize) -> ModInt { self.fact[n] } pub fn ifact(&self, n: usize) -> ModInt { self.ifact[n] } pub fn inv(&self, n: usize) -> ModInt { assert!(0 < n); self.inv[n] } pub fn perm(&self, n: usize, k: usize) -> ModInt { if k > n { return ModInt::zero(); } self.fact[n] * self.ifact[n - k] } pub fn binom(&self, n: usize, k: usize) -> ModInt { if n < k { return ModInt::zero(); } self.fact[n] * self.ifact[k] * self.ifact[n - k] } } // ---------- end precalc ---------- impl Zero for ModInt<{ M }> { fn zero() -> Self { Self::zero() } fn is_zero(&self) -> bool { self.0 == 0 } } impl One for ModInt<{ M }> { fn one() -> Self { Self::one() } fn is_one(&self) -> bool { self.get() == 1 } } // ---------- begin array op ---------- struct NTTPrecalc { sum_e: [ModInt<{ M }>; 30], sum_ie: [ModInt<{ M }>; 30], } impl NTTPrecalc<{ M }> { const fn new() -> Self { let cnt2 = (M - 1).trailing_zeros() as usize; let root = ModInt::new(ModInt::<{ M }>::PRIMITIVE_ROOT); let zeta = root.pow((M - 1) as u64 >> cnt2); let mut es = [ModInt::zero(); 30]; let mut ies = [ModInt::zero(); 30]; let mut sum_e = [ModInt::zero(); 30]; let mut sum_ie = [ModInt::zero(); 30]; let mut e = zeta; let mut ie = e.inv(); let mut i = cnt2; while i >= 2 { es[i - 2] = e; ies[i - 2] = ie; e = e.const_mul(e); ie = ie.const_mul(ie); i -= 1; } let mut now = ModInt::one(); let mut inow = ModInt::one(); let mut i = 0; while i < cnt2 - 1 { sum_e[i] = es[i].const_mul(now); sum_ie[i] = ies[i].const_mul(inow); now = ies[i].const_mul(now); inow = es[i].const_mul(inow); i += 1; } Self { sum_e, sum_ie } } } struct NTTPrecalcHelper; impl NTTPrecalcHelper { const A: NTTPrecalc = NTTPrecalc::new(); } pub trait ArrayAdd { type Item; fn add(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayAdd for [T] where T: Zero + Copy, { type Item = T; fn add(&self, rhs: &[Self::Item]) -> Vec { let mut c = vec![T::zero(); self.len().max(rhs.len())]; c[..self.len()].copy_from_slice(self); c.add_assign(rhs); c } } pub trait ArrayAddAssign { type Item; fn add_assign(&mut self, rhs: &[Self::Item]); } impl ArrayAddAssign for [T] where T: Add + Copy, { type Item = T; fn add_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() >= rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x + *a); } } impl ArrayAddAssign for Vec where T: Zero + Add + Copy, { type Item = T; fn add_assign(&mut self, rhs: &[Self::Item]) { if self.len() < rhs.len() { self.resize(rhs.len(), T::zero()); } self.as_mut_slice().add_assign(rhs); } } pub trait ArraySub { type Item; fn sub(&self, rhs: &[Self::Item]) -> Vec; } impl ArraySub for [T] where T: Zero + Sub + Copy, { type Item = T; fn sub(&self, rhs: &[Self::Item]) -> Vec { let mut c = vec![T::zero(); self.len().max(rhs.len())]; c[..self.len()].copy_from_slice(self); c.sub_assign(rhs); c } } pub trait ArraySubAssign { type Item; fn sub_assign(&mut self, rhs: &[Self::Item]); } impl ArraySubAssign for [T] where T: Sub + Copy, { type Item = T; fn sub_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() >= rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x = *x - *a); } } impl ArraySubAssign for Vec where T: Zero + Sub + Copy, { type Item = T; fn sub_assign(&mut self, rhs: &[Self::Item]) { if self.len() < rhs.len() { self.resize(rhs.len(), T::zero()); } self.as_mut_slice().sub_assign(rhs); } } pub trait ArrayDot { type Item; fn dot(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayDot for [T] where T: Mul + Copy, { type Item = T; fn dot(&self, rhs: &[Self::Item]) -> Vec { assert!(self.len() == rhs.len()); self.iter().zip(rhs).map(|p| *p.0 * *p.1).collect() } } pub trait ArrayDotAssign { type Item; fn dot_assign(&mut self, rhs: &[Self::Item]); } impl ArrayDotAssign for [T] where T: MulAssign + Copy, { type Item = T; fn dot_assign(&mut self, rhs: &[Self::Item]) { assert!(self.len() == rhs.len()); self.iter_mut().zip(rhs).for_each(|(x, a)| *x *= *a); } } pub trait ArrayMul { type Item; fn mul(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayMul for [T] where T: Zero + One + Copy, { type Item = T; fn mul(&self, rhs: &[Self::Item]) -> Vec { if self.is_empty() || rhs.is_empty() { return vec![]; } let mut res = vec![T::zero(); self.len() + rhs.len() - 1]; for (i, a) in self.iter().enumerate() { for (res, b) in res[i..].iter_mut().zip(rhs.iter()) { *res = *res + *a * *b; } } res } } // transform でlen=1を指定すればNTTになる pub trait ArrayConvolution { type Item; fn transform(&mut self, len: usize); fn inverse_transform(&mut self, len: usize); fn convolution(&self, rhs: &[Self::Item]) -> Vec; } impl ArrayConvolution for [ModInt<{ M }>] { type Item = ModInt<{ M }>; fn transform(&mut self, len: usize) { let f = self; let n = f.len(); let k = (n / len).trailing_zeros() as usize; assert!(len << k == n); assert!(k <= ModInt::<{ M }>::ORDER); let pre = &NTTPrecalcHelper::<{ M }>::A; for ph in 1..=k { let p = len << (k - ph); let mut now = ModInt::one(); for (i, f) in f.chunks_exact_mut(2 * p).enumerate() { let (x, y) = f.split_at_mut(p); for (x, y) in x.iter_mut().zip(y.iter_mut()) { let l = *x; let r = *y * now; *x = l + r; *y = l - r; } now *= pre.sum_e[(!i).trailing_zeros() as usize]; } } } fn inverse_transform(&mut self, len: usize) { let f = self; let n = f.len(); let k = (n / len).trailing_zeros() as usize; assert!(len << k == n); assert!(k <= ModInt::<{ M }>::ORDER); let pre = &NTTPrecalcHelper::<{ M }>::A; for ph in (1..=k).rev() { let p = len << (k - ph); let mut inow = ModInt::one(); for (i, f) in f.chunks_exact_mut(2 * p).enumerate() { let (x, y) = f.split_at_mut(p); for (x, y) in x.iter_mut().zip(y.iter_mut()) { let l = *x; let r = *y; *x = l + r; *y = (l - r) * inow; } inow *= pre.sum_ie[(!i).trailing_zeros() as usize]; } } let ik = ModInt::new(2).inv().pow(k as u64); for f in f.iter_mut() { *f *= ik; } } fn convolution(&self, rhs: &[Self::Item]) -> Vec { if self.len().min(rhs.len()) <= 32 { return self.mul(rhs); } const PARAM: usize = 10; let size = self.len() + rhs.len() - 1; let mut k = 0; while (size + (1 << k) - 1) >> k > PARAM { k += 1; } let len = (size + (1 << k) - 1) >> k; let mut f = vec![ModInt::zero(); len << k]; let mut g = vec![ModInt::zero(); len << k]; f[..self.len()].copy_from_slice(self); g[..rhs.len()].copy_from_slice(rhs); f.transform(len); g.transform(len); let mut buf = [ModInt::zero(); 2 * PARAM - 1]; let buf = &mut buf[..(2 * len - 1)]; let pre = &NTTPrecalcHelper::<{ M }>::A; let mut now = ModInt::one(); for (i, (f, g)) in f .chunks_exact_mut(2 * len) .zip(g.chunks_exact(2 * len)) .enumerate() { let mut r = now; for (f, g) in f.chunks_exact_mut(len).zip(g.chunks_exact(len)) { buf.fill(ModInt::zero()); for (i, f) in f.iter().enumerate() { for (buf, g) in buf[i..].iter_mut().zip(g.iter()) { *buf = *buf + *f * *g; } } f.copy_from_slice(&buf[..len]); for (f, buf) in f.iter_mut().zip(buf[len..].iter()) { *f = *f + r * *buf; } r = -r; } now *= pre.sum_e[(!i).trailing_zeros() as usize]; } f.inverse_transform(len); f.truncate(self.len() + rhs.len() - 1); f } } // ---------- end array op ---------- // ---------- begin trait ---------- use std::ops::*; pub trait Zero: Sized + Add { fn zero() -> Self; fn is_zero(&self) -> bool; } pub trait One: Sized + Mul { fn one() -> Self; fn is_one(&self) -> bool; } pub trait Group: Zero + Sub + Neg {} pub trait SemiRing: Zero + One {} pub trait Ring: SemiRing + Group {} pub trait Field: Ring + Div {} impl Group for T where T: Zero + Sub + Neg {} impl SemiRing for T where T: Zero + One {} impl Ring for T where T: SemiRing + Group {} impl Field for T where T: Ring + Div {} pub fn zero() -> T { T::zero() } pub fn one() -> T { T::one() } pub fn pow(mut r: T, mut n: usize) -> T { let mut t = one(); while n > 0 { if n & 1 == 1 { t = t * r.clone(); } r = r.clone() * r; n >>= 1; } t } pub fn pow_sum(mut r: T, mut n: usize) -> T { let mut ans = T::zero(); let mut sum = T::one(); while n > 0 { if n & 1 == 1 { ans = ans * r.clone() + sum.clone(); } sum = sum * (T::one() + r.clone()); r = r.clone() * r; n >>= 1; } ans } // ---------- end trait ---------- // ---------- begin segment tree Point Update Range Query ---------- pub struct SegmentTreePURQ { n: usize, size: usize, data: Vec, e: T, op: F, } impl SegmentTreePURQ where T: Clone, F: Fn(&T, &T) -> T, { pub fn new(n: usize, e: T, op: F) -> Self { assert!(n > 0); let size = n.next_power_of_two(); let data = vec![e.clone(); 2 * size]; SegmentTreePURQ { n, size, data, e, op, } } pub fn update_tmp(&mut self, x: usize, v: T) { assert!(x < self.n); self.data[x + self.size] = v; } pub fn update_all(&mut self) { for i in (1..self.size).rev() { self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]); } } pub fn update(&mut self, x: usize, v: T) { assert!(x < self.n); let mut x = x + self.size; self.data[x] = v; x >>= 1; while x > 0 { self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]); x >>= 1; } } pub fn find(&self, l: usize, r: usize) -> T { assert!(l <= r && r <= self.n); if l == r { return self.e.clone(); } let mut l = self.size + l; let mut r = self.size + r; let mut x = self.e.clone(); let mut y = self.e.clone(); while l < r { if l & 1 == 1 { x = (self.op)(&x, &self.data[l]); l += 1; } if r & 1 == 1 { r -= 1; y = (self.op)(&self.data[r], &y); } l >>= 1; r >>= 1; } (self.op)(&x, &y) } pub fn max_right

(&self, l: usize, f: P) -> usize where P: Fn(&T) -> bool, { assert!(l <= self.n); assert!(f(&self.e)); if l == self.n { return self.n; } let mut l = l + self.size; let mut sum = self.e.clone(); while { l >>= l.trailing_zeros(); let v = (self.op)(&sum, &self.data[l]); if !f(&v) { while l < self.size { l <<= 1; let v = (self.op)(&sum, &self.data[l]); if f(&v) { sum = v; l += 1; } } return l - self.size; } sum = v; l += 1; l.count_ones() > 1 } {} self.n } pub fn min_left

(&self, r: usize, f: P) -> usize where P: Fn(&T) -> bool, { assert!(r <= self.n); assert!(f(&self.e)); if r == 0 { return 0; } let mut r = r + self.size; let mut sum = self.e.clone(); while { r -= 1; while r > 1 && r & 1 == 1 { r >>= 1; } let v = (self.op)(&self.data[r], &sum); if !f(&v) { while r < self.size { r = 2 * r + 1; let v = (self.op)(&self.data[r], &sum); if f(&v) { sum = v; r -= 1; } } return r + 1 - self.size; } sum = v; (r & (!r + 1)) != r } {} 0 } } // ---------- end segment tree Point Update Range Query ---------- // ---------- begin Lazy Segment Tree ---------- pub trait TE { type T: Clone; type E: Clone; fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T; fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T; fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E; fn e(&self) -> Self::T; fn id(&self) -> Self::E; } pub struct LazySegmentTree { n: usize, size: usize, bit: u32, op: R, data: Vec<(R::T, R::E)>, } impl LazySegmentTree { pub fn new(n: usize, op: R) -> Self { assert!(n > 0); let size = n.next_power_of_two(); let bit = size.trailing_zeros(); let data = vec![(op.e(), op.id()); 2 * size]; Self { n, size, bit, op, data, } } pub fn build(init: I, n: usize, op: R) -> Self where I: Iterator, { let mut seg = Self::new(n, op); for (data, ini) in seg.data[seg.size..].iter_mut().zip(init) { data.0 = ini; } for i in (1..seg.size).rev() { seg.pull(i); } seg } pub fn update(&mut self, l: usize, r: usize, f: R::E) { assert!(l <= r && r <= self.n); if l == r { return; } self.push_range(l, r); let mut s = l + self.size; let mut t = r + self.size; while s < t { if s & 1 == 1 { self.apply(s, &f); s += 1; } if t & 1 == 1 { t -= 1; self.apply(t, &f); } s >>= 1; t >>= 1; } let l = l + self.size; let r = r + self.size; for k in 1..=self.bit { if (l >> k) << k != l { self.pull(l >> k); } if (r >> k) << k != r { self.pull((r - 1) >> k); } } } pub fn find(&mut self, l: usize, r: usize) -> R::T { assert!(l <= r && r <= self.n); if l == r { return self.op.e(); } self.push_range(l, r); let mut l = l + self.size; let mut r = r + self.size; let mut p = self.op.e(); let mut q = self.op.e(); while l < r { if l & 1 == 1 { p = self.op.fold(&p, &self.data[l].0); l += 1; } if r & 1 == 1 { r -= 1; q = self.op.fold(&self.data[r].0, &q); } l >>= 1; r >>= 1; } self.op.fold(&p, &q) } pub fn set_at(&mut self, x: usize, v: R::T) { assert!(x < self.n); let x = x + self.size; for k in (1..=self.bit).rev() { self.push(x >> k); } self.data[x].0 = v; for k in 1..=self.bit { self.pull(x >> k); } } pub fn max_right

(&mut self, l: usize, f: P) -> usize where P: Fn(&R::T) -> bool, { assert!(l <= self.n); assert!(f(&self.op.e())); if l == self.n { return self.n; } self.push_range(l, self.n); let mut l = l + self.size; let mut sum = self.op.e(); while { l >>= l.trailing_zeros(); let v = self.op.fold(&sum, &self.data[l].0); if !f(&v) { while l < self.size { self.push(l); l <<= 1; let v = self.op.fold(&sum, &self.data[l].0); if f(&v) { sum = v; l += 1; } } return l - self.size; } sum = v; l += 1; l.count_ones() > 1 } {} self.n } pub fn min_left

(&mut self, r: usize, f: P) -> usize where P: Fn(&R::T) -> bool, { assert!(r <= self.n); assert!(f(&self.op.e())); if r == 0 { return 0; } self.push_range(0, r); let mut r = r + self.size; let mut sum = self.op.e(); while { r -= 1; while r > 1 && r & 1 == 1 { r >>= 1; } let v = self.op.fold(&self.data[r].0, &sum); if !f(&v) { while r < self.size { self.push(r); r = 2 * r + 1; let v = self.op.fold(&self.data[r].0, &sum); if f(&v) { sum = v; r -= 1; } } return r + 1 - self.size; } sum = v; (r & (!r + 1)) != r } {} 0 } fn push_range(&mut self, l: usize, r: usize) { let l = l + self.size; let r = r + self.size; for k in (1..(self.bit + 1)).rev() { if (l >> k) << k != l { self.push(l >> k); } if (r >> k) << k != r { self.push((r - 1) >> k); } } } fn apply(&mut self, x: usize, f: &R::E) { self.data[x].0 = self.op.eval(&self.data[x].0, f); self.data[x].1 = self.op.merge(&self.data[x].1, f); } fn push(&mut self, x: usize) { let f = std::mem::replace(&mut self.data[x].1, self.op.id()); self.apply(2 * x, &f); self.apply(2 * x + 1, &f); } fn pull(&mut self, x: usize) { self.data[x].0 = self.op.fold(&self.data[2 * x].0, &self.data[2 * x + 1].0); } } // ---------- end Lazy Segment Tree ----------