package main import ( "bufio" "fmt" "os" "strconv" ) func configure(scanner *bufio.Scanner) { scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 1000005), 1000005) } func getNextString(scanner *bufio.Scanner) string { scanned := scanner.Scan() if !scanned { panic("scan failed") } return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func getNextFloat64(scanner *bufio.Scanner) float64 { i, _ := strconv.ParseFloat(getNextString(scanner), 64) return i } func main() { fp := os.Stdin wfp := os.Stdout extra := 0 if os.Getenv("I") == "IronMan" { fp, _ = os.Open(os.Getenv("END_GAME")) extra = 100 } scanner := bufio.NewScanner(fp) configure(scanner) writer := bufio.NewWriter(wfp) defer func() { r := recover() if r != nil { fmt.Fprintln(writer, r) } writer.Flush() }() solve(scanner, writer) for i := 0; i < extra; i++ { fmt.Fprintln(writer, "-----------------------------------") solve(scanner, writer) } } func solve(scanner *bufio.Scanner, writer *bufio.Writer) { n := getNextInt(scanner) q := getNextInt(scanner) aa := make([]int, n) seg := NewLazySegTree(n, E, ID) for i := 0; i < n; i++ { aa[i] = getNextInt(scanner) } ss := make([]int, n+1) add := make([][3]int, 0) for q > 0 { q-- c := getNextString(scanner) x := getNextInt(scanner) - 1 y := getNextInt(scanner) if c == "A" { add = append(add, [3]int{x, y, seg.Prod(x, x+1).(*S).x}) continue } seg.ApplyRange(x, y, &F{x: 1}) ss[x]++ ss[y]-- } bb := make([]int, n) for i := 0; i < n; i++ { ss[i+1] += ss[i] } for i := 0; i < n; i++ { bb[i] += aa[i] * ss[i] } for _, p := range add { bb[p[0]] += p[1] * (ss[p[0]] - p[2]) } sep := "" for i := 0; i < n; i++ { fmt.Fprintf(writer, "%s%d", sep, bb[i]) sep = " " } fmt.Fprintln(writer, "") } type S struct { x int } func (s *S) Op(l, r SInterface) SInterface { ll, rr := l.(*S), r.(*S) s.x = ll.x + rr.x return s } func (s *S) Mapping(l FInterface, r SInterface) SInterface { ll, rr := l.(*F), r.(*S) s.x = rr.x + ll.x return s } func (s *S) E() { s.x = 0 } func E() SInterface { var s S s.E() return &s } type F struct { x int } func (f *F) Composition(l, r FInterface) FInterface { ll, rr := l.(*F), r.(*F) f.x = ll.x + rr.x return f } func (f *F) ID() { f.x = 0 } func ID() FInterface { var f F f.ID() return &f } // SInterface Type S interface type SInterface interface { Op(SInterface, SInterface) SInterface Mapping(FInterface, SInterface) SInterface E() } // FInterface Type F interface type FInterface interface { Composition(FInterface, FInterface) FInterface ID() } // LazySegTree is the data structure for monoids type LazySegTree struct { n, size, log int e func() SInterface id func() FInterface d []SInterface lz []FInterface sml, smr SInterface } // NewLazySegTree Constructor func NewLazySegTree(n int, e func() SInterface, id func() FInterface) *LazySegTree { a := make([]SInterface, n) for i := 0; i < n; i++ { a[i] = e() } return NewLazySegTreeWithData(a, e, id) } // NewLazySegTreeWithData Constructor func NewLazySegTreeWithData(a []SInterface, e func() SInterface, id func() FInterface) *LazySegTree { n := len(a) log := 0 for i := n; i > 0; i >>= 1 { log++ } size := 1 << log d := make([]SInterface, size<<1) lz := make([]FInterface, size) for i := 0; i < size<<1; i++ { d[i] = e() } for i := 0; i < size; i++ { lz[i] = id() } for i := 0; i < n; i++ { d[i+size] = a[i] } s := LazySegTree{d: d, lz: lz, n: n, size: size, log: log, e: e, id: id, sml: e(), smr: e()} for i := size - 1; i > 0; i-- { s.update(i) } return &s } // Set assigns x to a[p] func (s *LazySegTree) Set(p int, x SInterface) { p += s.size for i := s.log; i > 0; i-- { s.push(p >> i) } s.d[p] = x for i := 1; i <= s.log; i++ { s.update(p >> i) } } // Get returns a[p] func (s *LazySegTree) Get(p int) SInterface { p += s.size for i := s.log; i > 0; i-- { s.push(p >> i) } return s.d[p] } // Prod returns op(a[l], ..., a[r - 1]), assuming the properties of the monoid. It returns e() if l = r. func (s *LazySegTree) Prod(l, r int) SInterface { if l >= r { return s.e() } s.sml.E() s.smr.E() l += s.size r += s.size for i := s.log; i > 0; i-- { if (l>>i)<> i) } if (r>>i)<> i) } } for l < r { if l&1 == 1 { s.sml.Op(s.sml, s.d[l]) l++ } if r&1 == 1 { r-- s.smr.Op(s.d[r], s.smr) } l >>= 1 r >>= 1 } return s.sml.Op(s.sml, s.smr) } // AllProd returns op(a[0], ..., a[n - 1]), assuming the properties of the monoid. It returns e() if n = 0. func (s *LazySegTree) AllProd() SInterface { return s.d[1] } // Apply applies a[p] = op_st(a[p], x). func (s *LazySegTree) Apply(p int, f FInterface) { p += s.size for i := s.log; i > 0; i-- { s.push(p >> i) } s.d[p].Mapping(f, s.d[p]) for i := 1; i <= s.log; i++ { s.update(p >> i) } } // ApplyRange applies a[p] = op_st(a[p], x) for all i = l..r-1. func (s *LazySegTree) ApplyRange(l, r int, f FInterface) { if l == r { return } l += s.size r += s.size for i := s.log; i > 0; i-- { if (l>>i)<> i) } if (r>>i)<> i) } } ll := l rr := r for l < r { if l&1 == 1 { s.allApply(l, f) l++ } if r&1 == 1 { r-- s.allApply(r, f) } l >>= 1 r >>= 1 } l = ll r = rr for i := 1; i <= s.log; i++ { if (l>>i)<> i) } if (r>>i)<> i) } } } // MaxRight returns an index r that satisfies both of the following. // r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true // r = n or f(op(a[l], a[l + 1], ..., a[r])) = false func (s *LazySegTree) MaxRight(l int, f func(x SInterface) bool) int { if l == s.n { return s.n } l += s.size for i := s.log; i > 0; i-- { s.push(l >> uint(i)) } s.sml.E() s.smr.E() for { for l&1 == 0 { l >>= 1 } if !f(s.smr.Op(s.sml, s.d[l])) { for l < s.size { s.push(l) l <<= 1 if f(s.smr.Op(s.sml, s.d[l])) { s.sml, s.smr = s.smr, s.sml l++ } } return l - s.size } s.sml.Op(s.sml, s.d[l]) l++ if l&-l == l { break } } return s.n } // MinLeft returns an index l that satisfies both of the following. // l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true // l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false func (s *LazySegTree) MinLeft(r int, f func(x SInterface) bool) int { if r == 0 { return 0 } r += s.size for i := s.log; i > 0; i-- { s.push((r - 1) >> uint(i)) } s.sml.E() s.smr.E() for { r-- for r > 1 && r&1 == 1 { r >>= 1 } if !f(s.smr.Op(s.sml, s.d[r])) { for r < s.size { s.push(r) r = r<<1 + 1 if f(s.smr.Op(s.sml, s.d[r])) { s.sml, s.smr = s.smr, s.sml r-- } } return r + 1 - s.size } s.sml.Op(s.sml, s.d[r]) if r&-r == r { break } } return 0 } func (s *LazySegTree) update(k int) { s.d[k].Op(s.d[k<<1], s.d[k<<1+1]) } func (s *LazySegTree) allApply(k int, f FInterface) { s.d[k].Mapping(f, s.d[k]) if k < s.size { s.lz[k].Composition(f, s.lz[k]) } } func (s *LazySegTree) push(k int) { s.allApply(k<<1, s.lz[k]) s.allApply(k<<1+1, s.lz[k]) s.lz[k].ID() }