Submission #50851673

---

Source Code Expand

class ST
	def initialize a,e,&op
		@l = (1<<(a.size-1).bit_length)
		@a = [e]*@l+a
		@a<<e
		@op = op
		((@l+a.size-1)/2).downto(1){|i|
			@a[i] = @op[*@a[i+i,2]]
		}
	end

	def [] l,r
		return if r<l
		l,r = l+@l,r+@l
		al = @a[l]
		ar = @a[r]
		while l+1<r
			al = @op[al,@a[l+1]] if l&1<1
			ar = @op[@a[r-1],ar] if 0<r&1
			l,r = l/2,r/2
		end
		return l==r ? al : @op[al,ar]
	end

	def []= i,v
		i += @l
		@a[i] = v
		@a[i] = @op[*@a[i+i,2]] while 0<i/=2
		return v
	end
end

N,Q = gets.split.map(&:to_i)
A = 0,*gets.split.map(&:to_i)
XSYT = ST.new(A.map{|a| [a,1,0,0] },[0,0,0,0]){|(x,a,y,b),(v,c,w,d)|
	t = Hash.new 0
	t[x] += a
	t[y] += b
	t[v] += c
	t[w] += d
	x,y = *t.keys.sort.reverse,0
	next x,t[x],y,t[y]
}
Q.times{
	q,a,b = gets.split.map(&:to_i)
	case q
	when 1
		XSYT[a] = [b,1,0,0]
	when 2
		puts XSYT[a,b][3]
	end
}

Submission Info

Judge Result