結果

問題 No.875 Range Mindex Query
ユーザー universatouniversato
提出日時 2020-05-29 08:46:36
言語 Ruby
(3.3.0)
結果
AC  
実行時間 1,148 ms / 2,000 ms
コード長 4,904 bytes
コンパイル時間 109 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 24,064 KB
最終ジャッジ日時 2024-10-14 07:37:26
合計ジャッジ時間 11,696 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 93 ms
12,160 KB
testcase_01 AC 101 ms
12,160 KB
testcase_02 AC 101 ms
12,288 KB
testcase_03 AC 93 ms
12,288 KB
testcase_04 AC 98 ms
12,160 KB
testcase_05 AC 98 ms
12,160 KB
testcase_06 AC 101 ms
12,160 KB
testcase_07 AC 100 ms
12,288 KB
testcase_08 AC 100 ms
12,160 KB
testcase_09 AC 96 ms
12,160 KB
testcase_10 AC 100 ms
12,288 KB
testcase_11 AC 1,148 ms
20,352 KB
testcase_12 AC 913 ms
17,664 KB
testcase_13 AC 929 ms
23,424 KB
testcase_14 AC 906 ms
22,912 KB
testcase_15 AC 1,143 ms
23,936 KB
testcase_16 AC 1,029 ms
23,808 KB
testcase_17 AC 1,099 ms
24,064 KB
testcase_18 AC 1,078 ms
24,064 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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

  # O(n)
  def initialize(n, form)
    
    @form = form
    case form
    when "and"
      @identity_element = 2 ** n - 1
      @func = Proc.new{|x, y| x & y }
    when "gcd"
      @identity_element = 0
      @func = Proc.new{|x, y| x.gcd y }
    when "max"
      @identity_element = -( inf = 10 ** 12 )
      @func = Proc.new{|x, y| x > y ? x : y }
    when "min"
      @identity_element = ( inf = 10 ** 12 )
      @func = Proc.new{|x, y| x < y ? x : y }
    when "or"
      @identity_element = 0
      @func = Proc.new{|x, y| x | y}
    when "prod"
      @identity_element = 1
      @func = Proc.new{|x, y| x * y}
    when "sum"
      @identity_element = 1
      @func = Proc.new{|x, y| x + y}
    end
    
    # @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(i, val)
    # @n-1: inner node size
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) / 2
      @nodes[i] = @func.call(@nodes[2*i+1], @nodes[2*i+2])
    end
    # p self
    self
  end
  
  def swap(i, j)
    # @n-1: inner node size
    n_i = @nodes[i + @n-1].dup
    n_j = @nodes[j + @n-1].dup
    update(i, n_j)
    update(j, n_i)
  end

  def get(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if l[0] == 0
        lres = @func.call(lres, @nodes[l])
        l += 1
      end
      if r[0] == 0
        r -= 1
        rres = @func.call(rres, @nodes[r])
      end
      l /= 2
      r /= 2
    end
    # p [lres, rres]
    return @func.call(lres, rres)
  end
  
  def [](k)
    @nodes[@n - 1 + k]
  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(form)
    st = SegmentTree.new(size, form)
    each_with_index{ |t, i| st.update(i, t) }
    st
  end
end

# f = Proc.new{|x, y| x.gcd y }
# p f.call(6, 10)
# p f.call(5, 15)
# p f.call(24,36)

# p st = [7,6,8].to_st("gcd")

# 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

# puts ""

# ABC 157
# n = gets.to_s.to_i
# s = gets.to_s.chomp
# q = gets.to_s.to_i

# st = SegmentTree.new(n, 0)

# # p "a".ord #=> 97
# s.bytes.each_with_index do |c, i|
#   st.update_or(i, 1 << (c-97))
# end

# q.times do

#   t, x, y = gets.to_s.split

#   if t == "1"
#     i, c = x.to_i-1, y[0].ord
#     st.update_or(i, 1 << (c-97))
#   else
#     l, r = x.to_i-1, y.to_i-1
#     puts st.get_or(l, r+1).to_s(2).count('1')
#   end
# end

#
# n = gets.to_s.to_i
# s = gets.to_s.chomp
# q = gets.to_s.to_i

# # sts = Array.new(26){ SegmentTree.new(n, form: :sum) }
# st = SegmentTree.new(n, form: :set)
# # p st
# # p "a".ord #=> 97
# s.chars.each_with_index do |c, i|
#   # sts[c - 97].update_sum(i, c)
#   st.update_sum(i, Set[c])
# end
# # p st
# q.times do

#   t, x, y = gets.to_s.split

#   if t == '1'
#     i, c = x.to_i-1, y.ord
#     st.update_sum(i, Set[y])
#   else
#     l, r = x.to_i-1, y.to_i-1
#     # p st
#     puts st.get_sum(l, r+1).size
#   end
# end

#  ABC125 C - GCD on Blackboard
# n = gets.to_s.to_i
# a = gets.to_s.split.map{|t| t.to_i }

# st = a.to_st(:gcd)
# ans = [st.get_gcd(1, n), st.get_gcd(0, n-1)].max

# 1.upto(n-2) do |i|
#   v = st.get_gcd(0, i).gcd st.get_gcd(i+1, n)
#   ans = v if ans < v
# end

# puts ans

# DSL_2_A
# 蟻本　python セグメント木　競技プログラミング　Atcoder - じゅっぴーダイアリー
# https://juppy.hatenablog.com/entry/2019/05/02/%E8%9F%BB%E6%9C%AC_python_%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder

# DSL_2_A
# n, q = gets.to_s.split.map{|t|t.to_i}
# st = SegmentTree.new(n)

# q.times do

#   c, x, y = gets.to_s.split
#   c, x, y = c.to_i, x.to_i, y.to_i

#   if c.zero?
#     st.update_min(x, y)
#   else
#     puts st.get_min(x, y+1)
#   end
# end

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

idx = Array.new(n+1)
a.each_with_index{ |t, i| idx[t] = i }

st = a.to_st("min")

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