#627047 (Crystal) No.1234 典型RMQ

• 問題: No.1234 典型RMQ
• ユーザー: tamura2004
• 提出日時: 2021-03-09 21:01:11
• 言語: Crystal (1.11.2)
• 結果: AC
• 実行時間: 446 ms / 2,000 ms
• コード長: 4,772 bytes
• コンパイル時間: 14,499 ms
• コンパイル使用メモリ: 296,092 KB
• 実行使用メモリ: 30,592 KB
• 最終ジャッジ日時: 2024-04-26 11:51:46
• 合計ジャッジ時間: 24,701 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	434 ms; 25,600 KB
testcase_07	AC	364 ms; 5,376 KB
testcase_08	AC	446 ms; 20,224 KB
testcase_09	AC	418 ms; 16,768 KB
testcase_10	AC	440 ms; 17,024 KB
testcase_11	AC	434 ms; 25,472 KB
testcase_12	AC	407 ms; 14,464 KB
testcase_13	AC	368 ms; 6,656 KB
testcase_14	AC	410 ms; 14,592 KB
testcase_15	AC	405 ms; 14,592 KB
testcase_16	AC	440 ms; 17,024 KB
testcase_17	AC	407 ms; 14,464 KB
testcase_18	AC	344 ms; 5,376 KB
testcase_19	AC	446 ms; 17,024 KB
testcase_20	AC	277 ms; 30,592 KB
testcase_21	AC	437 ms; 25,472 KB
testcase_22	AC	299 ms; 20,480 KB
testcase_23	AC	299 ms; 20,352 KB
testcase_24	AC	297 ms; 20,352 KB
testcase_25	AC	299 ms; 20,480 KB
testcase_26	AC	296 ms; 20,480 KB
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB
testcase_29	AC	2 ms; 5,376 KB

ソースコード

alias X = Int64
alias A = Int64

fxx = Proc(X,X,X).new do |x,y|
  Math.min(x,y)
end

fxa = Proc(X,A,X).new do |x,a|
  x + a
end

faa = Proc(A,A,A).new do |a,b|
  a + b
end

n = gets.to_s.to_i
a = gets.to_s.split.map(&.to_i64)
st = LazySegmentTree(X,A).new(fxx,fxa,faa,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

# 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]


# 遅延評価セグメント木
#
# ```
# # 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 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