Submission #24412768

---

Source Code Expand

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

	def [] l,r
		lm,rm = @h[l+=@l],@h[r+=@l]
		l,r,lm,rm = l/2,r/2-1,[@h[l],lm].min,[@h[r],rm].min until r<l
		return [lm,rm].min
	end
	def is l,r
		is,i0,w,m = [0],0,@l+1,self[l,r]
		until w<2 || is.empty?
			i0 += (@l+1)/w
			w /= 2
			is = is.inject([]){|a,i|
				a<<i if m==@h[i0+i+=i]
				a<<i if m==@h[i0+i+=1]
				next a
			}
			is.shift while is[0] && is[0]*w+w<=l
			is.pop while is[-1] && r<is[-1]*w
		end
		return is
	end

	def []= i,v
		i += @l
		@h[i] = v
		@h[i] = @h[i+i+1,2].min while 0<=i=(i-1)/2
		return v
	end
end

N,Q = gets.split.map(&:to_i)
A = 10**9,*gets.split.map(&:to_i)
M = ST.new A

Q.times{
	t,x,y = gets.split.map(&:to_i)
	if t<2
		M[x] = A[x] = y if A[x]!=y
	else
		is = M.is x,y
		print is.size,' ',is*' ',"\n"
	end
}

Submission Info

Judge Result