Submission #43229129

---

Source Code Expand

class BIT
	def initialize a,n
		@a = a
		@n = n+1 # accessing 0..n-1, 1..n internally.
	end

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

	def add i,d
		i += 1
		while i<@n
			@a[i] += d
			i += i&-i
		end
	end
	def inc i; add i,1 end
	def dec i; add i,-1 end
end

Qry = gets.to_i.times.map{
	gets.split.map(&:to_i)
}
Xs = Qry.map{_2}.compact.uniq.sort
I = Xs.each_with_index.to_h

A = []
X = BIT.new [0]*(I.size+1),I.size
T = Hash.new w = 0
DT = Hash.new 0
XOR = BIT.new Hash.new(0),1<<30
Qry.each{|c,x|
	case c
	when 1
		DT[x] += 1
	when 2
		DT[x] -= 1
	else
		DT.each{|x,d|
			next if d==0
			ix = I[x]
			t = T[x]
			T[x] += d
			w += 1 if t<2 && 1<T[x]
			w -= 1 if 1<t && T[x]<2
			if t<1
				X.inc ix
				xv = X[ix]
				l = Xs[X.lb xv-1]
				r = Xs[X.lb(xv+1)||I.size]
				XOR.inc l^x if 0<T[l] && l<x
				XOR.inc x^r if r
				XOR.dec l^r if 0<T[l] && l<x && r
			end
			if T[x]<1
				xv = X[ix]
				l = Xs[X.lb xv-1]
				r = Xs[X.lb(xv+1)||I.size]
				X.dec ix
				XOR.dec l^x if 0<T[l] && l<x
				XOR.dec x^r if r
				XOR.inc l^r if 0<T[l] && l<x && r
			end
		}.clear
		A.push 0<w ? 0 : XOR.lb(1)
	end
}

puts A

Submission Info

Judge Result