結果

問題 No.1234 典型RMQ
コンテスト
ユーザー tamura2004
提出日時 2021-03-09 21:10:01
言語 Crystal
(1.14.0)
結果
AC  
実行時間 446 ms / 2,000 ms
コード長 4,495 bytes
コンパイル時間 12,928 ms
コンパイル使用メモリ 298,676 KB
実行使用メモリ 30,464 KB
最終ジャッジ日時 2024-11-09 02:44:58
合計ジャッジ時間 24,360 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = gets.to_s.to_i
a = gets.to_s.split.map(&.to_i64)
st = LazySegmentTree(Int64,Int64).range_add_range_min(a)

q = gets.to_s.to_i
q.times do
  k,l,r,c = gets.to_s.split.map(&.to_i)
  c = c.to_i64
  l -= 1
  r -= 1
  case k
  when 1
    st[l..r] = c
  when
    pp st[l..r]
  end
end
# 遅延評価セグメント木
#
# ```
# # range add range sum
# alias Pair = Tuple(Int64, Int64)
# st = LazySegmentTree(Pair, Int64).new(
#   Proc(Pair, Pair, Pair).new { |(x, n), (y, m)| Pair.new x + y, n + m },
#   Proc(Pair, Int64, Pair).new { |(x, n), a| Pair.new x + n * a, n },
#   Proc(Int64, Int64, Int64).new { |a, b| a + b },
#   n: 4,
#   init: Pair.new(0_i64, 1_i64)
# ) # => [0, 0, 0, 0]
# st[..2] = 2_i64 # => [2, 2, 2, 0]
# st[2..] = 3_i64 # => [2, 2, 5, 3]
# st[1..2] = 4_i64 # => [2, 6, 9, 3]
# st[0..].should eq Pair.new(20_i64, 4_i64)
# # ```
class LazySegmentTree(X, A)
  getter n : Int32
  getter x : Array(X?)
  getter a : Array(A?)
  getter fxx : Proc(X?, X?, X?)
  getter fxa : Proc(X?, A?, X?)
  getter faa : Proc(A?, A?, A?)

  def self.range_add_range_min(_x)
    new(
      Proc(X,X,X).new { |x,y| Math.min x, y },
      Proc(X,A,X).new { |x,a| x + a },
      Proc(A,A,A).new { |a,b| a + b },
      _x
    )
  end

  def initialize(
    fxx : Proc(X,X,X),
    fxa : Proc(X,A,X),
    faa : Proc(A,A,A),
    n : Int32,
    init : X? = nil
    )
    x = Array(X?).new(n, init)
    initialize(fxx, fxa, faa, x)
  end
  
  def initialize(
    fxx : Proc(X,X,X),
    fxa : Proc(X,A,X),
    faa : Proc(A,A,A),
    _x : Array(X?)
  )
    @fxx = Proc(X?, X?, X?).new do |x, y|
      x && y ? fxx.call(x, y) : x ? x : y ? y : nil
    end

    @fxa = Proc(X?, A?, X?).new do |x, a|
      x && a ? fxa.call(x, a) : x ? x : nil
    end

    @faa = Proc(A?, A?, A?).new do |a, b|
      a && b ? faa.call(a, b) : a ? a : b ? b : nil
    end

    @n = Math.max 2, Math.pw2ceil(_x.size)
    @x = Array(X?).new(@n*2, nil)
    @a = Array(A?).new(@n*2, nil)

    _x.each_with_index do |v, i|
      x[i + n] = v
    end

    (n - 1).downto(1) do |i|
      x[i] = @fxx.call x[lch(i)], x[rch(i)]
    end
  end

  def set(i : Int32, y : X?)
    i += n
    propagate_above(i)
    x[i] = y
    a[i] = nil
    recalc_above(i)
  end

  def [](i : Int32, y : X?)
    set(i, y)
  end

  def fold(i : Int32, j : Int32) : X?
    i += n
    j += n

    i0 = pa(i)
    j0 = pa(j) - 1

    propagate_above(i0)
    propagate_above(j0)

    left = nil.as(X?)
    right = nil.as(X?)
    while i < j
      if i.odd?
        left = fxx.call left, eval(i)
        i += 1
      end
      if j.odd?
        j -= 1
        right = fxx.call eval(j), right
      end
      i >>= 1
      j >>= 1
    end
    fxx.call left, right
  end

  def [](r : Range(Int32?, Int32?)) : X?
    lo = r.begin || 0
    hi = (r.end || n - 1) + (r.excludes_end? ? 0 : 1)
    fold(lo, hi)
  end

  def [](r : Range(Int32?, Int32?), default : X) : X
    lo = r.begin || 0
    hi = (r.end || n - 1) + (r.excludes_end? ? 0 : 1)
    fold(lo, hi) || default
  end

  def update(i : Int32, j : Int32, b : A)
    i += n
    j += n

    i0 = pa(i)
    j0 = pa(j) - 1

    propagate_above(i0)
    propagate_above(j0)

    while i < j
      if i.odd?
        a[i] = faa.call a[i], b
        i += 1
      end
      if j.odd?
        j -= 1
        a[j] = faa.call a[j], b
      end
      i >>= 1
      j >>= 1
    end

    recalc_above(i0)
    recalc_above(j0)
  end

  def []=(r : Range(Int32?, Int32?), b : A)
    lo = r.begin || 0
    hi = (r.end || n - 1) + (r.excludes_end? ? 0 : 1)
    update(lo, hi, b)
  end

  def recalc_above(i)
    while i > 1
      i >>= 1
      x[i] = fxx.call eval(lch(i)), eval(rch(i))
    end
  end

  def propagate_above(i)
    return if i.zero?
    Math.ilogb(i).downto(1) do |n|
      propagate(i >> n)
    end
  end

  def propagate(i)
    return if a[i].nil?
    a[lch(i)] = faa.call a[lch(i)], a[i]
    a[rch(i)] = faa.call a[rch(i)], a[i]
    x[i] = eval(i)
    a[i] = nil
  end

  @[AlwaysInline]
  def eval(i : Int32) : X?
    fxa.call x[i], a[i]
  end

  @[AlwaysInline]
  def lch(i)
    i << 1
  end

  @[AlwaysInline]
  def rch(i)
    i << 1 | 1
  end

  @[AlwaysInline]
  def pa(i)
    i // (i & -i)
  end

  def pp
    puts "\n# node"
    i = 1
    while i <= n
      sep = " " * ((n * 2) // i - 1)
      puts x[i...(i << 1)].join(sep)
      i <<= 1
    end

    puts "\n# lazy"
    i = 1
    while i <= n
      sep = " " * ((n * 2) // i - 1)
      puts a[i...(i << 1)].join(sep)
      i <<= 1
    end
  end
end
0