結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー universato
提出日時 2020-05-28 23:41:02
言語 Ruby
(3.4.1)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,758 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 30,208 KB
最終ジャッジ日時 2024-10-13 14:24:07
合計ジャッジ時間 19,601 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 14 TLE * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

# 0-indexedで、getは半開区間であることに注意
class SegmentTree

  # O(n)
  # and :2^1-1
  # gcd :    1
  # max : -inf
  # min :  inf
  # or  :    0
  # prod:    1
  # set :   []
  # sum :    0
  def initialize(n, identity_element)
    @identity_element = identity_element
    @n = 1
    @n *= 2 while @n < n
    # @n: leaf node size(2^k)
    # @n*2-1: tree node size
    @nodes = Array.new(@n*2-1){ @identity_element }
  end

  def update_gcd(i, val)
    # @n-1: inner node size
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) / 2
      @nodes[i] = @nodes[2*i+1].gcd @nodes[2*i+2]
    end
  end

  def update_min(i, val)
    # @n-1: inner node size
    
    i += @n - 1
    # p [i]
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) / 2
      @nodes[i] = [@nodes[2*i+1], @nodes[2*i+2]].min
    end
  end

  def update_or(i, val)
    # @n-1: inner node size
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) / 2
      @nodes[i] = @nodes[2*i+1] | @nodes[2*i+2]
    end
  end

  def update_set(i, val)
    # @n-1: inner node size
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) / 2
      @nodes[i] = @nodes[2*i+1] + @nodes[2*i+2]
    end
  end

  def update_sum(i, val)
    # @n-1: inner node size
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) / 2
      @nodes[i] = @nodes[2*i+1] + @nodes[2*i+2]
    end
  end
  
  def swap_min(i, j)
    # @n-1: inner node size
    n_i = @nodes[i + @n-1].dup
    n_j = @nodes[j + @n-1].dup
    n_i[-1] = j
    n_j[-1] = i
    update_min(i, n_j)
    update_min(j, n_i)
  end

  def get_gcd(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if l[0] == 0
        lres = lres.gcd @nodes[l]
        l += 1
      end
      if r[0] == 0
        r -= 1
        rres = (@nodes[r]).gcd rres
      end
      l /= 2
      r /= 2
    end
    return lres.gcd(rres)
  end

  def get_min(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if l[0] == 0
        lres = @nodes[l] if lres > @nodes[l]
        l += 1
      end
      if r[0] == 0
        r -= 1
        rres = @nodes[r] if rres > @nodes[r]
      end
      l /= 2
      r /= 2
    end
    return lres < rres ? lres : rres
  end

  def get_or(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if l[0] == 0
        lres |= @nodes[l]
        l += 1
      end
      if r[0] == 0
        r -= 1
        rres |= @nodes[r]
      end
      l /= 2
      r /= 2
    end
    return lres | rres
  end

  def get_sum(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if l[0] == 0
        lres += @nodes[l]
        l += 1
      end
      if r[0] == 0
        r -= 1
        rres += @nodes[r]
      end
      l /= 2
      r /= 2
    end
    return lres + rres
  end

  def inspect

    t = 0
    res = "SegmentTree\n  "
    @nodes.each_with_index do |e,i|

      res << e.to_s << " "
      if t == i && i < @n-1
        res << "\n  "
        t = t * 2 + 2
      end
    end
    res
  end
end

class Array
  include Comparable
  def to_st(identity_element)
    st = SegmentTree.new(size, identity_element)
    each_with_index{ |t, i| st.update_min(i, t) }
    st
  end
end

n, q = gets.to_s.split.map{|t| t.to_i }
a    = gets.to_s.split.map{|t| t.to_i }

inf = [n + 1, nil]
# st = SegmentTree.new(n, inf)
st = a.map.with_index{|t, i| [t, i] }.to_st(inf)

q.times do
  x, l, r = gets.to_s.split.map{|t| t.to_i - 1 }
  # p "aaa"
  if x == 0
    st.swap_min(l, r)
  else
    # puts "ans:"
    p st.get_min(l, r+1)[-1] + 1
  end
end
0