結果

問題 No.875 Range Mindex Query
ユーザー universatouniversato
提出日時 2020-05-29 18:36:22
言語 Crystal
(1.11.2)
結果
AC  
実行時間 194 ms / 2,000 ms
コード長 2,447 bytes
コンパイル時間 18,069 ms
コンパイル使用メモリ 256,304 KB
実行使用メモリ 14,512 KB
最終ジャッジ日時 2023-09-13 10:38:57
合計ジャッジ時間 20,725 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,408 KB
testcase_01 AC 3 ms
4,624 KB
testcase_02 AC 4 ms
4,712 KB
testcase_03 AC 2 ms
4,480 KB
testcase_04 AC 3 ms
4,468 KB
testcase_05 AC 3 ms
4,540 KB
testcase_06 AC 3 ms
4,544 KB
testcase_07 AC 3 ms
4,788 KB
testcase_08 AC 3 ms
4,556 KB
testcase_09 AC 3 ms
4,528 KB
testcase_10 AC 4 ms
4,716 KB
testcase_11 AC 139 ms
14,512 KB
testcase_12 AC 113 ms
8,304 KB
testcase_13 AC 95 ms
12,088 KB
testcase_14 AC 92 ms
10,464 KB
testcase_15 AC 129 ms
12,148 KB
testcase_16 AC 180 ms
12,244 KB
testcase_17 AC 194 ms
12,128 KB
testcase_18 AC 192 ms
12,040 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree

  @n : (Int64|Int32)
  @n_1 : (Int64|Int32)
  @nodes : Array(Int64)
  @identity_element : Int64

  def initialize(n, form)
    
    @identity_element =  0_i64
    @func = Proc(Int64, Int64, Int64).new{|x, y| x + y }
    case form
    when "gcd"
      @identity_element = 0_i64
      @func = Proc(Int64, Int64, Int64).new{|x, y| x.gcd y }
    when "min"
      @identity_element =  (1_i64 << 60) - 1
      @func = Proc(Int64, Int64, Int64).new{|x, y| x < y ? x : y }
    when "or"
    #if form == "or"
      @identity_element =  0_i64
      @func = Proc(Int64, Int64, Int64).new{|x, y| x | y }
    end
    
    
    @n = 1
    while @n < n
      @n *= 2
    end
    @n_1 = @n - 1
    @nodes = Array(Int64).new(@n*2-1, @identity_element)
  end

  def all_update
    @n_1.downto(1){ |i| @nodes[i-1] = @func.call(@nodes[2*i-1], @nodes[2*i]) }
  end

  def update(i, val)
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) >> 1
      @nodes[i] = @func.call(@nodes[2*i+1], @nodes[2*i+2])
    end
  end

  def [](i)
    @nodes[@n_1 + i]
  end

  def []=(i, val)
    @nodes[@n_1 + i] = val
  end
 
  def get(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if 0 == ( l & 1 )
        lres = @func.call(@nodes[l], lres)
        l += 1
      end
      if 0 == ( r & 1 )
        r -= 1
        rres = @func.call(@nodes[r], rres)
      end
      l >>= 1
      r >>= 1
    end
    return @func.call(lres, rres)
  end
end

class Array
  def to_st(form)
    st = SegmentTree.new(size, form)
    each_with_index{ |t, i| st[i] = t }
    st.all_update
    st
  end
end

# yukicoder
n, q = gets.to_s.split.map{|t| t.to_i64 }
a    = gets.to_s.split.map{|t| t.to_i64 }

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

st = a.to_st("min")

q.times do
  x, l, r = gets.to_s.split.map{|t| t.to_i64 }
  l -= 1
  r -= 1

  if x == 1
    nl = st[l]
    nr = st[r]
    idx[nl] = r
    idx[nr] = l
    st.update(l, nr)
    st.update(r, nl)
  else
    puts (idx[st.get(l, r+1)] + 1)
  end
end

#n = gets.to_s.to_i
#s = gets.to_s.chomp
#q = gets.to_s.to_i
# 
## p "a".ord #=> 97
#st = s.chars.map{|c| 1_i64 << (c-'a') }.to_st("or")
#
#q.times do
# 
#  t, x, y = gets.to_s.split
# 
# if t == "1"
#    i, c = x.to_i-1, y[0].ord
#    st.update(i, 1_i64 << (c-97))
#  else
#    l, r = x.to_i-1, y.to_i-1
#    puts st.get(l, r+1).popcount
#  end
#end
0