Submission #28790707

---

Source Code Expand

class BIT
	def initialize n
		@a = [0]*(n+1)
	end
 
	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end
	def index s
		i,t,b,z = 0,0,1<<(@a.size-1).bit_length,@a.size
		t += @a[i|=b] if i|b<z && t+@a[i|b]<s while 0 < b>>=1
		return i if s<=self[i]
	end
 
	def add i,d
		i += 1
		z = @a.size
		while i<z
			@a[i] += d
			i += i&-i
		end
	end
end

L,Q = gets.split.map(&:to_i)
Qry = $<.map{|ln| ln.split.map(&:to_i) }
X = 0,*Qry.map(&:last).uniq.sort,L
I = X.each_with_index.to_h
W = BIT.new I.size+1
W.add I[L],I[L]
Qry.each{|c,x|
	i = I[x]
	if c<2
		w = W[i]
		j = W.index w+1
		d = i-w
		W.add j,-d
		W.add i,d
	else
		w = W[i]
		i = W.index w
		j = W.index w+1
		puts X[j]-X[i]
	end
}

Submission Info

Judge Result