#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::<usize>(); let (n, q) = (v[0], v[1]); let a = read_vec::<i64>(); let mut queries = vec![]; for _ in 0..q { let v = read_vec::<usize>(); let (t, l, r) = (v[0], v[1], v[2]); queries.push((t, l, r)); } let mut accum = vec![0; n + 1]; for i in 0..n { accum[i + 1] = accum[i] + a[i]; } let mut bit = BinaryIndexTree::new(n + 2); for i in 1..=n { bit.add(i, 1); } for (t, l, r) in queries { if t == 1 { for _ in 0..r - l { let i = get_index(l + 1, n, &mut bit); bit.add(i, -1); } } else { let l = get_index(l, n, &mut bit); let r = get_index(r + 1, n, &mut bit) - 1; let ans = accum[r] - accum[l - 1]; println!("{}", ans); } } } fn get_index(x: usize, n: usize, bit: &BinaryIndexTree) -> usize { let (ok, ng) = binary_search(0, n + 1, |mid: usize| { if mid == n + 1 { false } else { bit.sum(mid) < x as i64 } }); ng } struct BinaryIndexTree { bit: Vec<i64>, n: usize, } impl BinaryIndexTree { fn new(n: usize) -> BinaryIndexTree { BinaryIndexTree { bit: vec![0; n + 1], n: n, } } fn sum(&self, i: usize) -> i64 { // assert!(i > 0); let mut i = i; let mut s = 0i64; while i > 0 { s += self.bit[i]; i -= (i as i64 & -(i as i64)) as usize; } s } fn add(&mut self, i: usize, x: i64) { assert!(i > 0); let mut i = i; while i <= self.n { self.bit[i as usize] += x; i += (i as i64 & -(i as i64)) as usize; } } } fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } type Input = usize; fn binary_search<F>(lb: Input, ub: Input, mut criterion: F) -> (Input, Input) where F: FnMut(Input) -> bool, { assert_eq!(criterion(lb), true); assert_eq!(criterion(ub), false); let mut ok = lb; let mut ng = ub; while ng - ok > 1 { let mid = (ng + ok) / 2; if criterion(mid) { ok = mid; } else { ng = mid; } } (ok, ng) }