//---------- begin SegmentTree Point update Range query ---------- mod segment_tree { pub struct PURQ T> { n: usize, a: Vec, id: T, op: F, } #[allow(dead_code)] impl T> PURQ { pub fn new(n: usize, id: T, op: F) -> PURQ { let mut k = 1; while k < n { k *= 2; } PURQ { n: k, a: vec![id.clone(); 2 * k], id: id, op: op, } } pub fn update(&mut self, x: usize, v: T) { let mut k = self.n + x; let a = &mut self.a; a[k] = v; k >>= 1; while k > 0 { a[k] = (self.op)(a[2 * k].clone(), a[2 * k + 1].clone()); k >>= 1; } } pub fn update_tmp(&mut self, x: usize, v: T) { self.a[x + self.n] = v; } pub fn update_all(&mut self) { for k in (1..(self.n)).rev() { self.a[k] = (self.op)(self.a[2 * k].clone(), self.a[2 * k + 1].clone()); } } pub fn find(&self, mut l: usize, mut r: usize) -> T { let mut p = self.id.clone(); let mut q = self.id.clone(); l += self.n; r += self.n; while l < r { if (l & 1) == 1 { p = (self.op)(p, self.a[l].clone()); l += 1; } if (r & 1) == 1 { r -= 1; q = (self.op)(self.a[r].clone(), q); } l >>= 1; r >>= 1; } (self.op)(p, q) } } } //---------- end SegmentTree Point update Range query ---------- //---------- begin scannner ---------- #[allow(dead_code)] mod scanner { use std::str::FromStr; use std::str::SplitWhitespace; use std::io::Read; use std; pub struct Scanner<'a> { it: SplitWhitespace<'a> } impl<'a> Scanner<'a> { pub fn new(s: &'a String) -> Scanner<'a> { Scanner { it: s.split_whitespace() } } pub fn next(&mut self) -> T { match self.it.next().unwrap().parse::() { Ok(v) => v, _ => panic!("Scanner error") } } pub fn next_chars(&mut self) -> Vec { self.next::().chars().collect() } } pub fn read_string() -> String { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s } } //---------- end scannner ---------- use std::io::Write; fn main() { let sc = scanner::read_string(); let sc = scanner::Scanner::new(&sc); let out = std::io::stdout(); let out = std::io::BufWriter::new(out.lock()); run(sc, out); } fn run(mut sc: scanner::Scanner, mut out: std::io::BufWriter) { let n: usize = sc.next(); let q: usize = sc.next(); let mut a: Vec = Vec::with_capacity(n); for _ in 0..n { a.push(sc.next()); } a.push(0); for i in (1..n).rev() { a[i] -= a[i - 1]; } let f = |a, b| a + b; let mut s = segment_tree::PURQ::new(n, 0, f); for i in 1..n { if 0 != a[i] { s.update(i, 1); } } for _ in 0..q { let op: u8 = sc.next(); let l = sc.next::(); let r = sc.next::(); if op == 1 { let x: i64 = sc.next(); let l = l - 1; if l > 0 && a[l] == 0 { s.update(l, 1); } if r < n && a[r] == 0 { s.update(r, 1); } a[l] += x; a[r] -= x; if l > 0 && a[l] == 0 { s.update(l, 0); } if r < n && a[r] == 0 { s.update(r, 0); } } else { let ans = 1 + if l < r {s.find(l, r)} else {0}; writeln!(out, "{}", ans).unwrap(); } } }