結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー tamura2004
提出日時 2020-03-07 09:58:41
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 1,843 bytes
記録
コンパイル時間 67 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 29,952 KB
最終ジャッジ日時 2024-10-14 11:58:10
合計ジャッジ時間 8,608 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:82: warning: assigned but unused variable - n
Syntax OK

ソースコード

diff #
raw source code 

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][1],seg[i][1] = seg[i][1],seg[j][1]
    _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