Submission #38082557

---

Source Code Expand

class ST
	def initialize a
		@l = (1<<(a.size-1).bit_length)-1
		@t = [[a[-1],a[-1],true]]*@l+a.map{|v| [v,v,true] }
		((@l+a.size-2)/2).downto(0){|i|
			(m1,x1,b1),(m2,x2,b2) = @t[i+i+1,2]
			@t[i] = [[m1,m2].min,[x1,x2].max,x1<=m2&&b1&&b2]
		}
		@t<<[a[-1],a[-1],true]
	end

	def inspect
		i,z,*a = 0,1
		while i<@t.size
			a<<@t[i,z].inspect
			i,z = i+z,z+z
		end
		return a*"\n"
	end
	def [] l,r
		return if r<l
		return @t[l+@l] if l==r
		lm,lx,lb = @t[l+=@l]
		rm,rx,rb = @t[r+=@l]
		l1,r1 = (l-1)/2,(r-1)/2
		while l1<r1
			if 0<l&1
				m1,x1,b1 = @t[l+1]
				lm,lx,lb = [lm,m1].min,[lx,x1].max,lx<=m1&&lb&&b1
			end
			if r&1<1
				m1,x1,b1 = @t[r-1]
				rm,rx,rb = [rm,m1].min,[rx,x1].max,x1<=rm&&rb&&b1
			end
			l,r,l1,r1 = l1,r1,(l1-1)/2,(r1-1)/2
		end
		return [lm,rm].min,[lx,rx].max,lx<=rm&&lb&&rb
	end

	def []= i,v
		i += @l
		@t[i] = [v,v,true]
		while 0<=i=(i-1)/2
			(m1,x1,b1),(m2,x2,b2) = @t[i+i+1,2]
			@t[i] = [[m1,m2].min,[x1,x2].max,x1<=m2&&b1&&b2]
		end
		return v
	end
end

N = gets.to_i
S = gets.chomp
R = ST.new S.chars
A = []
gets.to_i.times{
	q,a1,a2 = gets.split
	case q.to_i
	when 1
		x,c = a1.to_i-1,a2
		R[x] = c
#		S[x] = c
#warn S
	when 2
		l,r = a1.to_i-1,a2.to_i-1
#warn '"%s[%s]%s" %s'%[S[0...l],S[l..r],S[r+1..],R[l,r].inspect]
		A<<(R[l,r][2]?'Yes':'No')
	when 3
#warn R.inspect
	end
}
puts A

Submission Info

Judge Result