Submission #47966425

---

Source Code Expand

class BIT
	def initialize n
		@a = [1]*(n+1) # 1-indexed internally
		1.upto(n){|i|
			j = i+(i&-i)
			@a[j] += @a[i] if j<=n
		}
	end

	def [] i
		i += 1
		s = 0
		while 0<i
			s += @a[i]
			i &= i-1
		end
		return s
	end
	def lb s
		z = @a.size-1
		i,t,b = 0,0,1<<z.bit_length
		t += @a[i|=b] if i|b<=z && t+@a[i|b]<s while 0<b >>= 1
		return i if i<z # i は１大きい内部インデックス(もしくは 0)だけど、求めた添字が s より小さい値を返す最大の添字であり、s 以上を返す最小の添字としては +1 したものを返したいから、足し引きして内部インデックスそのままの値を返す(アクセス可能な範囲(0..z-1)なら)。
	end
 
	def add i,d
		i += 1
		while i<@a.size
			@a[i] += d
			i += i&-i
		end
	end
	def inc i; add i,1 end
	def dec i; add i,-1 end
end

(N,Q),A,*Qry = $<.map{|ln| ln.split.map(&:to_i) }
X = (A|Qry.map{_2}).sort
X.pop while X[0]&&X.size<=X[-1]
Z = X.size
M = BIT.new Z
T = [0]*Z
A.each{|a|
	M.dec a if a<Z && 1==T[a] += 1
}
A.unshift nil
puts Qry.map{|i,x|
	a,A[i] = A[i],x
	M.inc a if a<Z && 0==T[a] -= 1
	M.dec x if x<Z && 1==T[x] += 1
	next M.lb(1)||Z
}

Submission Info

Judge Result