提出 #48153886

---

ソースコード 拡げる

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

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

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

N,Q = gets.split.map(&:to_i)
S = gets.chomp.bytes
T = S.reverse
P = 2**29+11
Op1 = lambda{|b0|
	*pb = b = 1
	N.times{
		pb<<b = b*b0%P
	}
	lambda{|cl,cr,(sl,sr)|
		(sl+pb[cl]*sr)%P
	}
}[10**9+7]
S1 = ST.new S,0,&Op1
T1 = ST.new T,0,&Op1
A = []
Q.times{
	q,a1,a2 = gets.split
	case q.to_i
	when 1
		x,c = a1.to_i-1,a2.ord
		rx = N-1-x
		S1[x] = T1[rx] = c
	when 2
		l,r = a1.to_i-1,a2.to_i-1
		rl,rr = N-1-r,N-1-l
		A<<(S1[l,r]==T1[rl,rr]?'Yes':'No')
	end
}
puts A

提出情報

ジャッジ結果