Submission #48153685

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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
P = 2**50+55
Op = lambda{|b|
	lambda{|cl,cr,(sl,sr)|
		(sl+b.pow(cl,P)*sr)%P
	}
}

N,Q = gets.split.map(&:to_i)
S = gets.chomp.bytes
T = S.reverse
S1 = ST.new S,0,&Op[10**9+7]
T1 = ST.new T,0,&Op[10**9+7]
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

Submission Info

Judge Result