結果

問題 No.875 Range Mindex Query
ユーザー tamura2004tamura2004
提出日時 2020-03-07 10:21:02
言語 Ruby
(3.3.0)
結果
AC  
実行時間 931 ms / 2,000 ms
コード長 1,843 bytes
コンパイル時間 276 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 29,952 KB
最終ジャッジ日時 2024-04-22 12:33:18
合計ジャッジ時間 8,885 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
12,032 KB
testcase_01 AC 88 ms
12,288 KB
testcase_02 AC 86 ms
12,288 KB
testcase_03 AC 81 ms
12,160 KB
testcase_04 AC 82 ms
11,904 KB
testcase_05 AC 81 ms
12,160 KB
testcase_06 AC 88 ms
12,160 KB
testcase_07 AC 85 ms
12,160 KB
testcase_08 AC 81 ms
12,288 KB
testcase_09 AC 80 ms
12,160 KB
testcase_10 AC 84 ms
12,160 KB
testcase_11 AC 931 ms
27,264 KB
testcase_12 AC 761 ms
19,272 KB
testcase_13 AC 674 ms
29,568 KB
testcase_14 AC 672 ms
28,800 KB
testcase_15 AC 900 ms
29,696 KB
testcase_16 AC 772 ms
29,568 KB
testcase_17 AC 813 ms
29,696 KB
testcase_18 AC 803 ms
29,952 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:82: warning: assigned but unused variable - n
Syntax OK

ソースコード

diff # 

class SegTree
  attr_reader :size, :e, :f
  attr_accessor :seg

  def self.create(a=[],e,f)
    n = 1
    n *= 2 while n < a.size
    this = new(n,e,f)
    a.size.times do |i|
      this.seg[i+n] = a[i]
    end
    (n-1).downto(1) do |i|
      this.seg[i] = f[ this.seg[i*2],this.seg[i*2+1] ]
    end
    this
  end

  def initialize(n=2**32,e,f)
    @size = n
    @e = e
    @f = f
    @seg = Array.new(size*2, e)
  end

  def [](i)
    i += size
    seg[i]
  end

  def []=(i,x)
    i += size
    seg[i] = x
  end

  def update(i,x)
    i += size
    seg[i] = x
    _update(i)
  end
  
  def _update(i)
    while i > 1
      i /= 2
      seg[i] = f[ seg[i*2], seg[i*2+1] ]
    end
  end

  def swap(i,j)
    i += size
    j += size
    seg[j][0],seg[i][0] = seg[i][0],seg[j][0]
    _update(i)
    _update(j)
  end

  def query(a,b)
    ans = e
    a += size; b += size
    while a < b
      (ans = f[ ans, seg[a] ]; a += 1) if a.odd?
      (b -= 1; ans = f[ ans, seg[b] ]) if b.odd?
      a /= 2; b /= 2
    end
    ans
  end

  def inspect
    { size: size, seg: seg }.to_s
  end
end

# SegTree.new(N,E,F) := 要素数N、単位元E、演算Fで初期化、ただしNは2の冪
# SegTree.create(A,E,F) := モノイドA、単位元E、演算Fで初期化で初期化
# update(i,x) := A[i]をxに更新
# query(a,b) := 半開区間[a,b)でのA[i]の演算結果
#
# 単位元を追加してモノイドにする例（gcd）
# E = -1
# F = -> x,y { x == E ? y : y == E ? x : x.gcd(y) }
# T = SegTree.create(a,E,F)

n,m = gets.split.map &:to_i
a = gets.split.map &:to_i
a = a.map.with_index{|v,i|[v,i]}

E = [10**6, -1] # 値、インデックス
F = -> x,y { x[0] < y[0] ? x : y }
T = SegTree.create(a,E,F)

m.times do
  c,l,r = gets.split.map &:to_i
  if c == 1
    T.swap(l-1,r-1)
  else
    ans = T.query(l-1,r)
    puts ans[1]+1
  end
end
0