package main import ( "bufio" "fmt" "os" "sort" "strconv" ) var sc = bufio.NewScanner(os.Stdin) var wr = bufio.NewWriter(os.Stdout) func out(x ...interface{}) { fmt.Fprintln(wr, x...) } func getI() int { sc.Scan() i, e := strconv.Atoi(sc.Text()) if e != nil { panic(e) } return i } func getF() float64 { sc.Scan() i, e := strconv.ParseFloat(sc.Text(), 64) if e != nil { panic(e) } return i } func getInts(N int) []int { ret := make([]int, N) for i := 0; i < N; i++ { ret[i] = getI() } return ret } func getS() string { sc.Scan() return sc.Text() } // min, max, asub, absなど基本関数 func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b } func asub(a, b int) int { if a > b { return a - b } return b - a } func abs(a int) int { if a >= 0 { return a } return -a } func lowerBound(a []int, x int) int { idx := sort.Search(len(a), func(i int) bool { return a[i] >= x }) return idx } func upperBound(a []int, x int) int { idx := sort.Search(len(a), func(i int) bool { return a[i] > x }) return idx } func main() { defer wr.Flush() sc.Split(bufio.ScanWords) sc.Buffer([]byte{}, 1000000) // this template is new version. // use getI(), getS(), getInts(), getF() N, Q := getI(), getI() a := getInts(N) b := make([]int, N) c := make([]S, N) var e = func() S { return S{0} } var merger = func(a, b S) S { return S{a.a + b.a} } var mapper = func(f F, x S) S { return S{x.a + f.a} } var comp = func(f, g F) F { return F{f.a + g.a} } var id = func() F { return F{0} } seg := newLazySegtree(c, e, merger, mapper, comp, id) for i := 0; i < Q; i++ { c, x, y := getS(), getI(), getI() if c == "A" { x-- a[x] += y b[x] -= seg.Get(x).a * y } else { x-- seg.RangeApply(x, y, F{1}) // for j := 0; j < N; j++ { // fmt.Fprint(wr, seg.Get(j)) // } // out() } } for i := 0; i < N; i++ { val := b[i] + seg.Get(i).a*a[i] fmt.Fprint(wr, val, " ") } out() } type S struct { a int } type F struct { a int } type E func() S type Merger func(a, b S) S type Mapper func(f F, x S) S type Comp func(f, g F) F type Id func() F type Compare func(v S) bool type LazySegtree struct { n int size int log int d []S lz []F e E merger Merger mapper Mapper comp Comp id Id } func newLazySegtree(v []S, e E, merger Merger, mapper Mapper, comp Comp, id Id) *LazySegtree { lseg := new(LazySegtree) lseg.n = len(v) lseg.log = lseg.ceilPow2(lseg.n) lseg.size = 1 << uint(lseg.log) lseg.d = make([]S, 2*lseg.size) lseg.e = e lseg.lz = make([]F, lseg.size) lseg.merger = merger lseg.mapper = mapper lseg.comp = comp lseg.id = id for i, _ := range lseg.d { lseg.d[i] = lseg.e() } for i, _ := range lseg.lz { lseg.lz[i] = lseg.id() } for i := 0; i < lseg.n; i++ { lseg.d[lseg.size+i] = v[i] } for i := lseg.size - 1; i >= 1; i-- { lseg.Update(i) } return lseg } func (lseg *LazySegtree) Update(k int) { lseg.d[k] = lseg.merger(lseg.d[2*k], lseg.d[2*k+1]) } func (lseg *LazySegtree) AllApply(k int, f F) { lseg.d[k] = lseg.mapper(f, lseg.d[k]) if k < lseg.size { lseg.lz[k] = lseg.comp(f, lseg.lz[k]) } } func (lseg *LazySegtree) Push(k int) { lseg.AllApply(2*k, lseg.lz[k]) lseg.AllApply(2*k+1, lseg.lz[k]) lseg.lz[k] = lseg.id() } func (lseg *LazySegtree) Set(p int, x S) { p += lseg.size for i := lseg.log; i <= 1; i-- { lseg.Push(p >> uint(i)) } lseg.d[p] = x for i := 1; i <= lseg.log; i++ { lseg.Update(p >> uint(i)) } } func (lseg *LazySegtree) Get(p int) S { p += lseg.size for i := lseg.log; i >= 1; i-- { lseg.Push(p >> uint(i)) } return lseg.d[p] } func (lseg *LazySegtree) Prod(l, r int) S { if l == r { return lseg.e() } l += lseg.size r += lseg.size for i := lseg.log; i >= 1; i-- { if (l>>uint(i))<> uint(i)) } if (r>>uint(i))<> uint(i)) } } sml, smr := lseg.e(), lseg.e() for l < r { if (l & 1) == 1 { sml = lseg.merger(sml, lseg.d[l]) l++ } if (r & 1) == 1 { r-- smr = lseg.merger(lseg.d[r], smr) } l >>= 1 r >>= 1 } return lseg.merger(sml, smr) } func (lseg *LazySegtree) AllProd() S { return lseg.d[1] } func (lseg *LazySegtree) Apply(p int, f F) { p += lseg.size for i := lseg.log; i >= 1; i-- { lseg.Push(p >> uint(i)) } lseg.d[p] = lseg.mapper(f, lseg.d[p]) for i := 1; i <= lseg.log; i++ { lseg.Update(p >> uint(i)) } } func (lseg *LazySegtree) RangeApply(l int, r int, f F) { if l == r { return } l += lseg.size r += lseg.size for i := lseg.log; i >= 1; i-- { if (l>>uint(i))<> uint(i)) } if (r>>uint(i))<> uint(i)) } } l2, r2 := l, r for l < r { if l&1 == 1 { lseg.AllApply(l, f) l++ } if r&1 == 1 { r-- lseg.AllApply(r, f) } l >>= 1 r >>= 1 } l, r = l2, r2 for i := 1; i <= lseg.log; i++ { if (l>>uint(i))<> uint(i)) } if (r>>uint(i))<> uint(i)) } } } func (lseg *LazySegtree) MaxRight(l int, cmp Compare) int { if l == lseg.n { return lseg.n } l += lseg.size for i := lseg.log; i >= 1; i-- { lseg.Push(l >> uint(i)) } sm := lseg.e() for { for l%2 == 0 { l >>= 1 } if !cmp(lseg.merger(sm, lseg.d[l])) { for l < lseg.size { lseg.Push(l) l = 2 * l if cmp(lseg.merger(sm, lseg.d[l])) { sm = lseg.merger(sm, lseg.d[l]) l++ } } return l - lseg.size } sm = lseg.merger(sm, lseg.d[l]) l++ if l&-l == l { break } } return lseg.n } func (lseg *LazySegtree) MinLeft(r int, cmp Compare) int { if r == 0 { return 0 } r += lseg.size for i := lseg.log; i >= 1; i-- { lseg.Push(r - 1>>uint(i)) } sm := lseg.e() for { r-- for r > 1 && r%2 != 0 { r >>= 1 } if !cmp(lseg.merger(lseg.d[r], sm)) { for r < lseg.size { lseg.Push(r) r = 2*r + 1 if cmp(lseg.merger(lseg.d[r], sm)) { sm = lseg.merger(lseg.d[r], sm) r-- } } return r + 1 - lseg.size } sm = lseg.merger(lseg.d[r], sm) if r&-r == r { break } } return 0 } func (lseg *LazySegtree) ceilPow2(n int) int { x := 0 for (1 << uint(x)) < n { x++ } return x }