package main import ( "bufio" "fmt" "os" "sort" "strconv" ) func out(x ...interface{}) { fmt.Println(x...) } var sc = bufio.NewScanner(os.Stdin) func getInt() int { sc.Scan() i, e := strconv.Atoi(sc.Text()) if e != nil { panic(e) } return i } func getInts(N int) []int { ret := make([]int, N) for i := 0; i < N; i++ { ret[i] = getInt() } return ret } func getString() 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() { sc.Split(bufio.ScanWords) sc.Buffer([]byte{}, 1000000) N, Q := getInt(), getInt() a := make([]S, N) for i := 0; i < N; i++ { a[i] = S{getInt()} } segL := SegtreeInit(N, 0) for i := 1; i < N; i++ { if a[i].a == a[i-1].a { segL.Set(i-1, 1) } } segL.Update() seg := newLazySegtree(a, e, merger, mapper, comp, id) for i := 0; i < Q; i++ { op := getInt() if op == 1 { l, r, x := getInt()-1, getInt()-1, getInt() seg.RangeApply(l, r+1, F{x}) if l != 0 { p := seg.Prod(l-1, l) q := seg.Prod(l, l+1) if p.a == q.a { segL.UpdateAt(l-1, 1) } else { segL.UpdateAt(l-1, 0) } } if r != N-1 { p := seg.Prod(r, r+1) q := seg.Prod(r+1, r+2) if p.a == q.a { segL.UpdateAt(r, 1) } else { segL.UpdateAt(r, 0) } } } else { l, r := getInt()-1, getInt()-1 p := int(segL.Query(l, r+1)) out(r - l + 1 - p) } // for j := 0; j < N; j++ { // fmt.Print(seg.Prod(j, j+1), " ") // } // for j := 0; j < N; j++ { // fmt.Print(segL.Query(j, j+1), " ") // } // fmt.Println() } } func e() S { return S{-1} } func merger(l, r S) S { if l.a > r.a { return l } return r } func mapper(f F, x S) S { return S{x.a + f.a} } func comp(f, g F) F { return F{f.a + g.a} } func id() F { return F{0} } 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 } /* セグメント木(2020.05.24作成) SegtreeInitで初期化 Setで値設定し、Updateで木作成 Getで値を取得 UpdateAtで個別のアイテムを更新 Queryで区間の値を取得 compareで比較方法変更可能 */ // Data : // Data型をstructすれば複数データが持てる // compareも変更すること! type Data int // SegmentTree : type SegmentTree struct { inf Data d []Data offset int } // SegtreeInit : nが要素数、valが初期値 func SegtreeInit(n int, val Data) *SegmentTree { var ret SegmentTree size := 1 for size < n { size *= 2 } ret.d = make([]Data, size*2) for i := 1; i < size*2; i++ { ret.d[i] = val } ret.offset = size ret.inf = val return &ret } // Set : 要素に値をセット(※木は更新されない) func (s *SegmentTree) Set(idx int, val Data) { s.d[s.offset+idx] = val } // Get : 要素に値を取得 func (s *SegmentTree) Get(idx int) Data { return s.d[s.offset+idx] } // Update : func (s *SegmentTree) Update() { N := s.offset off := s.offset for N > 1 { for i := off; i < off+N; i += 2 { p := i / 2 l := i r := i + 1 s.d[p] = s.compare(s.d[l], s.d[r]) } off /= 2 N /= 2 } } // querySub : // a, b ... 範囲 func (s *SegmentTree) querySub(a, b, k, l, r int) Data { if r <= a || b <= l { return s.inf } if a <= l && r <= b { return s.d[k] } return s.compare( s.querySub(a, b, k*2, l, (l+r)/2), s.querySub(a, b, k*2+1, (l+r)/2, r)) } // Query : // a, b ... 範囲 a <= x < bの範囲で検索 // [a, b)となっているのに注意 func (s *SegmentTree) Query(a, b int) Data { return s.querySub(a, b, 1, 0, s.offset) } // UpdateAt : func (s *SegmentTree) UpdateAt(n int, val Data) { pos := s.offset + n s.d[pos] = val for pos > 1 { p := pos / 2 l := p * 2 r := p*2 + 1 s.d[p] = s.compare(s.d[l], s.d[r]) pos /= 2 } } // compare : // 比較関数(ここで比較方法を設定) // ※min,maxを入れ替えるときなどは、Initの設定注意 func (s *SegmentTree) compare(l, r Data) Data { // 区間の合計の場合はinitを0にして下記 return l + r // 区間のminの場合はinfに最大値以上を設定して下記 // if l < r { // return l // } // return r }