#[derive(Debug, Clone)] struct LazySegmentTree { n: usize, orgn: usize, unit: T, mem: Vec, lazy_unit: U, lazy: Vec, operator: F, mapper: G, composer: H, } impl LazySegmentTree where T: std::fmt::Debug + Copy, U: std::fmt::Debug + std::cmp::PartialEq + Copy, F: Fn(T, T) -> T, G: Fn(T, U) -> T, H: Fn(U, U) -> U, { fn new(n: usize, unit: T, lazy_unit: U, operator: F, mapper: G, composer: H) -> Self { let mut size = 1usize; while size < n { size *= 2; } Self { n: size, orgn: n, unit: unit, mem: vec![unit; size*2-1], lazy_unit: lazy_unit, lazy: vec![lazy_unit; size*2-1], operator: operator, mapper: mapper, composer: composer, } } fn find_closed(&mut self, l: usize, r: usize) -> T { self.find(l, r+1) } fn find(&mut self, l: usize, r: usize) -> T { self._find(l, r, 0, 0, self.n) } fn update_closed(&mut self, left: usize, right: usize, val: U) { self.update(left, right+1, val); } fn update(&mut self, left: usize, right: usize, val: U) { self._update(left, right, val, 0, 0, self.n); } fn get(&mut self, pos: usize) -> T { self.find_closed(pos, pos) } fn _evaluate(&mut self, k: usize) { if self.lazy[k] == self.lazy_unit { return; } if k < self.n-1 { let left = self._left(k); let right = self._right(k); self.lazy[left] = (self.composer)(self.lazy[left], self.lazy[k]); self.lazy[right] = (self.composer)(self.lazy[right], self.lazy[k]); } self.mem[k] = (self.mapper)(self.mem[k], self.lazy[k]); self.lazy[k] = self.lazy_unit; } fn _find(&mut self, a: usize, b: usize, nodenum: usize, l: usize, r: usize) -> T { self._evaluate(nodenum); if r <= a || b <= l { self.unit } else if a <= l && r <= b { self.mem[nodenum] } else { let left = self._find(a, b, self._left(nodenum), l, (l+r)/2); let right = self._find(a, b, self._right(nodenum), (l+r)/2, r); (self.operator)(left, right) } } fn _update(&mut self, a: usize, b: usize, x: U, nodenum: usize, l: usize, r: usize) { self._evaluate(nodenum); if a <= l && r <= b { self.lazy[nodenum] = (self.composer)(self.lazy[nodenum], x); self._evaluate(nodenum); } else if a < r && l < b { self._update(a, b, x, self._left(nodenum), l, (l + r) / 2); self._update(a, b, x, self._right(nodenum), (l + r) / 2, r); self.mem[nodenum] = (self.operator)(self.mem[self._left(nodenum)], self.mem[self._right(nodenum)]); } } fn _left(&self, k: usize) -> usize { 2*k+1 } fn _right(&self, k: usize) -> usize { 2*k+2 } fn _parent(&self, k: usize) -> usize { (k-1)/2 } } fn main() { let mut nq = String::new(); std::io::stdin().read_line(&mut nq).ok(); let nq: Vec = nq.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nq[0]; let q = nq[1]; let mut a = String::new(); std::io::stdin().read_line(&mut a).ok(); let a: Vec = a.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let queries = (0..q).map(|_| { let mut temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); let temp: Vec<&str> = temp.trim().split_whitespace().collect(); (temp[0].chars().nth(0).unwrap(), temp[1].parse::().unwrap(), temp[2].parse::().unwrap()) }) .collect::>(); let op = |x: usize, y: usize| { x + y }; let mut segtree = LazySegmentTree::new(n, 0usize, 0usize, op, op, op); let mut val_at_queriy = vec![0usize; q]; for (i, &(c, x, y)) in queries.iter().enumerate() { if c == 'A' { val_at_queriy[i] = segtree.get(x-1); } else { segtree.update_closed(x-1, y-1, 1); } } let mut result = vec![0usize; n]; for (i, &(c, x, y)) in queries.iter().enumerate() { if c == 'A' { result[x-1] += y * (segtree.get(x-1) - val_at_queriy[i]); } } for i in 0..n { result[i] += segtree.get(i) * a[i]; } println!("{}", result.into_iter().map(|v| v.to_string()).collect::>().join(" ")); }