結果

問題 No.875 Range Mindex Query
ユーザー universatouniversato
提出日時 2020-05-29 09:15:08
言語 Ruby
(3.3.0)
結果
AC  
実行時間 917 ms / 2,000 ms
コード長 2,707 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 24,192 KB
最終ジャッジ日時 2024-10-14 09:19:18
合計ジャッジ時間 9,017 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
12,288 KB
testcase_01 AC 96 ms
12,032 KB
testcase_02 AC 95 ms
12,416 KB
testcase_03 AC 92 ms
12,288 KB
testcase_04 AC 93 ms
12,160 KB
testcase_05 AC 92 ms
12,160 KB
testcase_06 AC 97 ms
12,160 KB
testcase_07 AC 96 ms
12,416 KB
testcase_08 AC 93 ms
12,160 KB
testcase_09 AC 93 ms
12,288 KB
testcase_10 AC 95 ms
12,288 KB
testcase_11 AC 917 ms
20,608 KB
testcase_12 AC 749 ms
17,536 KB
testcase_13 AC 662 ms
23,424 KB
testcase_14 AC 662 ms
23,040 KB
testcase_15 AC 873 ms
23,808 KB
testcase_16 AC 754 ms
24,064 KB
testcase_17 AC 805 ms
24,192 KB
testcase_18 AC 790 ms
24,192 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
    @n_1 = @n - 1
    @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
    true
  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 build
    @n_1.downto(1) do |i|
      @nodes[i-1] = @func.call(@nodes[2*i-1], @nodes[2*i])
    end
  end
  
  def [](k)
    @nodes[@n_1 + k]
  end
  
  def []=(i, val)
    @nodes[@n_1 + i] = val
  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
  def to_st(form)
    st = SegmentTree.new(size, form)
    each_with_index{ |t, i| st[i] = t }
    st.build
    st
  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")

ans = []
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
    ans << (idx[st.get(l, r+1)] + 1)
  end
end

puts ans
0