提出 #54386336

---

ソースコード 拡げる

END { load __FILE__ unless $stdin.eof? }

class Elem
  attr_accessor :ab, :a, :b, :l

  def initialize(a = 0, b = 0)
    @m = 998_244_353
    @ab, @a, @b, @l = (a * b) % @m, a, b, 1
  end

  def op(x, y)
    @ab = (x.ab + y.ab) % @m
    @a = (x.a + y.a) % @m
    @b = (x.b + y.b) % @m
    @l = (x.l + y.l) % @m
    self
  end

  def id
    @ab, @a, @b, @l = 0, 0, 0, 0
    self
  end

  def map(f)
    @ab = (@ab + @a * f.y + @b * f.x + @l * (f.x * f.y % @m)) % @m
    @a = (@a + @l * f.x) % @m
    @b = (@b + @l * f.y) % @m
    self
  end
end

class Func
  attr_accessor :x, :y

  def initialize(x = 0, y = 0)
    @m = 998_244_353
    @x, @y = x, y
  end

  def composite(f)
    @x = (f.x + @x) % @m
    @y = (f.y + @y) % @m
    self
  end

  def id
    @x, @y = 0, 0
    self
  end
end

module AtCoder
  class SegmentTree
    def initialize(ary_or_size = 0)
      ary =
      if ary_or_size.kind_of?(Integer)
        Array.new(ary_or_size) { id }
      else
        ary_or_size.to_a
      end
      @n = ary.size
      @log = @n.pred.bit_length
      @size = 1 << @log

      @ary = Array.new(@size * 2) { id }
      @ary[@size, @n] = ary
      @size.pred.downto(1) { |i| update(i) }

      @sml0 = id
      @smr0 = id
    end

    def op(x, y, z)
      z.op(x, y)
    end

    def id(z = Elem.new)
      z.id
    end

    def []=(idx, x)
      idx += @size
      @ary[idx] = x
      1.upto(@log) { |i| update(idx >> i) }
      x
    end

    def [](idx)
      @ary[idx + @size]
    end

    def prod(l, r)
      sml = id(@sml0)
      smr = id(@smr0)
      l += @size
      r += @size

      while l < r
        (sml = op(sml, @ary[l], sml); l += 1) if l.odd?
        (r -= 1; smr = op(@ary[r], smr, smr)) if r.odd?
        l >>= 1
        r >>= 1
      end

      op(sml, smr, sml)
    end

    def all_prod
      @ary[1]
    end

    private

    def update(k)
      @ary[k] = op(@ary[2 * k], @ary[2 * k + 1], @ary[k])
    end
  end

  class LazySegmentTree < SegmentTree
    def initialize(ary_or_size = 0)
      super
      @lz = Array.new(@size) { id_func }
    end

    def mapping(f, x)
      x.map(f)
    end

    def composition(f, g)
      g.composite(f)
    end

    def id_func(f = Func.new)
      f.id
    end

    def []=(idx, x)
      push_all(idx)
      super
    end

    def [](idx)
      push_all(idx)
      super
    end

    def prod(l, r)
      return id if l == r

      l2, r2 = l, r
      l += @size
      r += @size

      @log.downto(1) do |i|
        m = -1[0, i]
        push(l >> i) if l.anybits?(m)
        push(r >> i) if r.anybits?(m)
      end

      super(l2, r2)
    end

    def apply(l, r = l + 1, f)
      case r - l
      when 0
        return self
      when 1
        push_all(l)
        self[l] = mapping(f, self[l])
        return self
      end

      l += @size
      r += @size
      q = r - 1

      @log.downto(1) do |i|
        m = -1[0, i]
        push(l >> i) if l.anybits?(m)
        push(q >> i) if r.anybits?(m)
      end

      l2, r2 = l, r
      while l < r
        (all_apply(l, f); l += 1) if l.odd?
        (r -= 1; all_apply(r, f)) if r.odd?
        l >>= 1
        r >>= 1
      end
      l, r = l2, r2

      1.upto(@log) do |i|
        m = -1[0, i]
        update(l >> i) if l.anybits?(m)
        update(q >> i) if r.anybits?(m)
      end

      self
    end

    def apply_all(f)
      all_apply(1, f)
      self
    end

    private

    def all_apply(k, f)
      @ary[k] = mapping(f, @ary[k])
      @lz[k] = composition(f, @lz[k]) if k < @size
    end

    def push(k)
      all_apply(2 * k, @lz[k])
      all_apply(2 * k + 1, @lz[k])
      @lz[k] = id_func(@lz[k])
    end

    def push_all(idx)
      idx += @size
      @log.downto(1) { |i| push(idx >> i) }
    end
  end
end

n, q = gets.split.map!(&:to_i)
a = gets.split.map!(&:to_i)
b = gets.split.map!(&:to_i)

ary = Array.new(n) { |i| Elem.new(a[i], b[i]) }
st = AtCoder::LazySegmentTree.new(ary)
f = Func.new

q.times do

t, l, r, x = gets.split.map!(&:to_i)
l -= 1

case t
when 1
  f.x, f.y = x, 0
  st.apply(l, r, f)
when 2
  f.x, f.y = 0, x
  st.apply(l, r, f)
when 3
  puts st.prod(l, r).ab
end

end

__END__

提出情報

ジャッジ結果