Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
ARC 033-C データ構造
class BinaryIndexedTree
def initialize
@N=200_001
@bit=Array.new(@N){0}
end
def add(k, x)
while k<=@N
@bit[k]+=x
k+=(k&-k)
end
end
def sum(k)
ret=0
while k>0
ret+=@bit[k]
k-=(k&-k)
end
ret
end
end
q=gets.to_i
bt=BinaryIndexedTree.new
q.times do
t, x=gets.split.map(&:to_i)
case t
when 1
bt.add(x, 1)
when 2
l, u=0, 200_000
while u-l>1
m=(u+l)/2
bt.sum(m)<x ? l=m: u=m
end
puts u
bt.add(u, -1)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment