#![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 { data: Vec, lazy: Vec>, n: usize, } impl std::fmt::Debug for LazySegTree { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { let v = &self.data[self.n - 1..]; write!(f, "{:?}", v) } } impl LazySegTree { /// すべて単位元で埋めた長さ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::>(); 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] = Some(L::op( &lv, self.lazy[k * 2 + 1].as_ref().unwrap_or(&L::id()), )); self.lazy[k * 2 + 2] = Some(L::op( self.lazy[k * 2 + 2].as_ref().unwrap_or(&L::id()), &lv, )); } 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 { 1 } fn op(a: &usize, b: &usize) -> usize { *a.min(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::::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::>(); 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, 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, reader: std::io::BufReader, } 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(&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 { self.next::().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() } } }