Submission #50881793

---

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 += @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 /= 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)|
	if x<v
		if x<w
			[v,c,w,d]
		elsif w<x
			[v,c,x,a]
		else
			[v,c,x,a+d]
		end
	elsif v<x
		if y<v
			[x,a,v,c]
		elsif v<y
			[x,a,y,b]
		else
			[x,a,y,b+c]
		end
	else
		if y<w
			[x,a+c,w,d]
		elsif w<y
			[x,a+c,y,b]
		else
			[x,a+c,y,b+d]
		end
	end
}
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