結果

問題 No.875 Range Mindex Query
ユーザー universatouniversato
提出日時 2020-05-29 00:01:23
言語 Crystal
(1.11.2)
結果
AC  
実行時間 265 ms / 2,000 ms
コード長 3,491 bytes
コンパイル時間 18,727 ms
コンパイル使用メモリ 256,612 KB
実行使用メモリ 17,924 KB
最終ジャッジ日時 2023-09-13 10:38:11
合計ジャッジ時間 20,728 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,484 KB
testcase_01 AC 4 ms
4,768 KB
testcase_02 AC 4 ms
4,704 KB
testcase_03 AC 3 ms
4,512 KB
testcase_04 AC 4 ms
4,660 KB
testcase_05 AC 3 ms
4,528 KB
testcase_06 AC 4 ms
4,632 KB
testcase_07 AC 3 ms
4,680 KB
testcase_08 AC 3 ms
4,680 KB
testcase_09 AC 3 ms
4,520 KB
testcase_10 AC 4 ms
4,860 KB
testcase_11 AC 244 ms
14,740 KB
testcase_12 AC 168 ms
12,816 KB
testcase_13 AC 160 ms
17,052 KB
testcase_14 AC 154 ms
17,924 KB
testcase_15 AC 221 ms
16,960 KB
testcase_16 AC 237 ms
17,040 KB
testcase_17 AC 265 ms
17,076 KB
testcase_18 AC 251 ms
17,176 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree

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

  def initialize(n, identity_element)

    # or  :    0
    # min :  inf
    # max : -inf
    # set :   []
    # sum :    0
    # prod:    1
    # gcd :    1
    @identity_element = identity_element

    @n = 1
    while @n < n
      @n *= 2
    end

    @nodes = Array.new(@n*2-1){@identity_element}
  end

  def update_min(i, val)
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) >> 1
     @nodes[i] = {@nodes[2*i+1], @nodes[2*i+2]}.min
    end
  end

  def update_or(i, val)
    i += @n - 1
    @nodes[i] = val
    while i > 0
      i = ( i - 1 ) >> 1
      @nodes[i] = @nodes[2*i+1] | @nodes[2*i+2]
    end
  end

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

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

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

  def get_gcd(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if 0 == ( l & 1 )
        lres = lres.gcd @nodes[l]
        l += 1
      end
      if 0 == ( r & 1 )
        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 0 == ( l & 1 )
        lres = {lres, @nodes[l]}.min
        l += 1
      end
      if 0 == ( r & 1 )
        r -= 1
        rres = {@nodes[r], rres}.min
      end
      l //= 2
      r //= 2
    end
    return {lres, rres}.min
  end

  def get_sum(l, r)
    l += @n - 1
    r += @n - 1
    lres, rres = @identity_element, @identity_element
    while l < r
      if 0 == ( l & 1 )
        lres = lres + @nodes[l]
        l += 1
      end
      if 0 == ( r & 1 )
        r -= 1
        rres = rres + @nodes[r]
      end
      l //= 2
      r //= 2
    end
    return lres + rres
  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
end

class Array
  def to_segment_tree_for_gcd
    st = SegmentTree.new(size.to_i64, 0_i64)
    each_with_index{ |t, i| st.update_gcd(i, t) }
    st
  end
  def to_segment_tree_for_min(inf = 10 ** 12)
    st = SegmentTree.new(size, inf)
    each_with_index{ |t, i| st.update_min(i, t) }
    st
  end
  def to_segment_tree_for_sum
    st = SegmentTree.new(size, 0_i64)
    each_with_index{ |t, i| st.update_sum(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, 0]
# st = SegmentTree.new(n, inf)
st = a.map_with_index{|t, i| [t, i] }.to_segment_tree_for_min(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