def solve(io) n, q = io.get2 a = io.get_a(n, Int64) s = SegTree.new(a.map { |ai| Item.new(ai, ai, 1) }, Item.new(-1, -1, 0)) q.times do case io.get when 1 l, r, x = io.get(Int32, Int32, Int64); l -= 1; r -= 1 s.apply(l..r, SegTree::OpAdd.new(x)) when 2 l, r = io.get2; l -= 1; r -= 1 io.put s[l..r].b end end end record Item, l : Int64, r : Int64, b : Int32 class ProconIO def initialize(@ins : IO = STDIN, @outs : IO = STDOUT) @buf = IO::Memory.new("") end def get(k : T.class = Int32) forall T get_v(k) end macro define_get {% for i in (2..9) %} def get({{ *(1..i).map { |j| "k#{j}".id } }}) { {{ *(1..i).map { |j| "get(k#{j})".id } }} } end {% end %} end define_get macro define_getn {% for i in (2..9) %} def get{{i}}(k : T.class = Int32) forall T get({{ *(1..i).map { "k".id } }}) end {% end %} end define_getn def get_a(n : Int, k : T.class = Int32) forall T Array.new(n) { get_v(k) } end def get_c(n : Int, k : T.class = Int32) forall T get_a(n, k) end macro define_get_c {% for i in (2..9) %} def get_c(n : Int, {{ *(1..i).map { |j| "k#{j}".id } }}) a = Array.new(n) { get({{ *(1..i).map { |j| "k#{j}".id } }}) } { {{ *(1..i).map { |j| "a.map { |e| e[#{j-1}] }".id } }} } end {% end %} end define_get_c macro define_getn_c {% for i in (2..9) %} def get{{i}}_c(n : Int, k : T.class = Int32) forall T get_c(n, {{ *(1..i).map { "k".id } }}) end {% end %} end define_getn_c def get_m(r : Int, c : Int, k : T.class = Int32) forall T Array.new(r) { get_a(c, k) } end macro define_put {% for i in (1..9) %} def put({{ *(1..i).map { |j| "v#{j}".id } }}, *, delimiter = " ") {% for j in (1..i) %} print_v(v{{j}}, delimiter) {% if j < i %}@outs << delimiter{% end %} {% end %} @outs.puts end {% end %} end define_put def put_e(*vs) put(*vs) exit end def put_f(*vs) put(*vs) @outs.flush end private def get_v(k : Int32.class); get_token.to_i32; end private def get_v(k : Int64.class); get_token.to_i64; end private def get_v(k : UInt32.class); get_token.to_u32; end private def get_v(k : UInt64.class); get_token.to_u64; end private def get_v(k : Float64.class); get_token.to_f64; end private def get_v(k : String.class); get_token; end private def get_token loop do token = @buf.gets(' ', chomp: true) break token unless token.nil? @buf = IO::Memory.new(@ins.read_line) end end private def print_v(v, dlimiter) @outs << v end private def print_v(v : Enumerable, delimiter) v.each_with_index do |e, i| @outs << e @outs << delimiter if i < v.size - 1 end end end struct Int def cdiv(b : Int) (self + b - 1) // b end def bit?(i : Int) bit(i) == 1 end def set_bit(i : Int) self | (self.class.new(1) << i) end def reset_bit(i : Int) self & ~(self.class.new(1) << i) end {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "0.34.0") < 0 %} def bit_length : Int32 x = self < 0 ? ~self : self if x.is_a?(Int::Primitive) Int32.new(sizeof(self) * 8 - x.leading_zeros_count) else to_s(2).size end end {% end %} end struct Float64 def near_zero? self.abs < EPSILON end end struct Number {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "1.1.0") < 0 %} def zero? self == 0 end def positive? self > 0 end def negative? self < 0 end {% end %} {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "0.36.0") < 0 %} def self.additive_identity zero end def self.multiplicative_identity new(1) end {% end %} end class Array macro new_md(*args, &block) {% if !block %} {% for arg, i in args[0...-2] %} Array.new({{arg}}) { {% end %} Array.new({{args[-2]}}, {{args[-1]}}) {% for arg in args[0...-2] %} } {% end %} {% else %} {% for arg, i in args %} Array.new({{arg}}) { |_i{{i}}| {% end %} {% for block_arg, i in block.args %} {{block_arg}} = _i{{i}} {% end %} {{block.body}} {% for arg in args %} } {% end %} {% end %} end end module Math {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "1.2.0") < 0 %} def isqrt(value : Int::Primitive) raise ArgumentError.new "Input must be non-negative integer" if value < 0 return value if value < 2 res = value.class.zero bit = res.succ << (res.leading_zeros_count - 2) bit >>= value.leading_zeros_count & ~0x3 while (bit != 0) if value >= res + bit value -= res + bit res = (res >> 1) + bit else res >>= 1 end bit >>= 2 end res end {% end %} end macro min_u(a, b) {{a}} = Math.min({{a}}, {{b}}) end macro max_u(a, b) {{a}} = Math.max({{a}}, {{b}}) end macro zip(a, *b, &block) {{a}}.zip({{*b}}) {{block}} end abstract class SegmentTreeLazy(T) abstract class Op; end class OpNil < Op; end def initialize(@n : Int32, @init : T = T.zero) @an = 1 << (@n - 1).bit_length @sec = Array.new(@an << 1) { Section(T).new(@init) } init_propagate end def initialize(b : Array(T), @init : T = T.zero) @n = b.size @an = 1 << (@n - 1).bit_length @sec = Array.new(@an << 1) { Section(T).new(@init) } b.each_with_index do |bi, i| @sec[i + @an].val = bi end init_propagate end def compose(a : T, b : T) : T; @init; end def update_section(sec : Section, op : Op, s : Int) : NoReturn; end def [](start : Int, count : Int) l, r = start, start + count summary(l, r, 1, 0, @an) end def [](r : Range) sc = Indexable.range_to_index_and_count(r, @n) raise ArgumentError.new("Invalid range") if sc.nil? self[*sc] end def apply(r : Range, op : Op) sc = Indexable.range_to_index_and_count(r, @n) raise ArgumentError.new("Invalid range") if sc.nil? start, count = sc l, r = start, start + count apply(op, l, r, 1, 0, @an) end class Section(T) def initialize(@val : T) @op = OpNil.new end property val : T property op : Op end @an : Int32 @sec : Array(Section(T)) private def init_propagate (1...@an).reverse_each do |i| @sec[i].val = compose(@sec[i << 1].val, @sec[i << 1 | 1].val) end end private def summary(l : Int, r : Int, k : Int, nl : Int, nr : Int) return @init if nr <= l || r <= nl return @sec[k].val if l <= nl && nr <= r propagate(k, nl, nr) nm = (nl + nr) >> 1 vl = summary(l, r, k << 1 , nl, nm) vr = summary(l, r, k << 1 | 1, nm, nr) compose(vl, vr) end private def propagate(k : Int, nl : Int, nr : Int) return if @sec[k].op.is_a? OpNil nm = (nl + nr) >> 1 update_section(@sec[k << 1 ], @sec[k].op, nm - nl) update_section(@sec[k << 1 | 1], @sec[k].op, nr - nm) @sec[k].op = OpNil.new end private def apply(op : Op, l : Int, r : Int, k : Int, nl : Int, nr : Int) return if nr <= l || r <= nl if l <= nl && nr <= r update_section(@sec[k], op, nr - nl) return end propagate(k, nl, nr) nm = (nl + nr) >> 1 apply(op, l, r, k << 1 , nl, nm) apply(op, l, r, k << 1 | 1, nm, nr) @sec[k].val = compose(@sec[k << 1].val, @sec[k << 1 | 1].val) end end class SegTree < SegmentTreeLazy(Item) class OpAdd < Op def initialize(@val : Int64); end getter val : Int64 end def compose(a : Item, b : Item) if b.l == -1 a elsif a.l == -1 b else Item.new(a.l, b.r, a.b + b.b - (a.r == b.l ? 1 : 0)) end end def update_section(sec : Section(Item), op : Op, s : Int) forall U return if sec.val.l == -1 case op when OpAdd sec.val = Item.new(sec.val.l + op.val, sec.val.r + op.val, sec.val.b) sec.op = case prev = sec.op when OpAdd OpAdd.new(prev.val + op.val) else op end end end end solve(ProconIO.new)