結果

問題 No.3239 Omnibus
コンテスト
ユーザー 👑 p-adic
提出日時 2025-08-14 22:40:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,136 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 501 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 415,996 KB
最終ジャッジ日時 2025-08-14 22:41:40
合計ジャッジ時間 9,629 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 TLE * 3 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def copy(n):return n.copy()if hasattr(n,"copy")else n
def rec_str(a):return"".join(["[",", ".join(rec_str(x)for x in a),"]"])if isinstance(a,list)else str(a)
class DynamicBIT:
	e=[0,0] #User's definition
	op=lambda x,y:[x[0]+y[0],x[1]+y[1]] #User's definition
	inv=lambda x:[-x[0],-x[1]] #User's definition

	def __init__(self,N):
		self.N=N
		self.F={}
	def copy(self):
		a=__class__(0)
		a.N=__self__.N
		a.F=__copy(self__.F)
		return a
	def Add(self,i,u):
		if i<0:return
		i+=1
		while i<=self.N:
			self.Replace(i,__class__.op(self.Access(i),u))
			i+=i&-i
	def Set(self,i,u):self.Add(i,__class__.op(u,__class__.inv(self.Get(i))))
	def Get(self,i):
		assert 0<=i<self.N
		return self.IntervalSum(i,i)
	def InitialSegmentSum(self,r):
		assert -2<r<self.N
		a=copy(__class__.e)
		i=min(r+1,self.N)
		while i:
			a=__class__.op(a,self.Access(i))
			i-=i&-i
		return a
	def IntervalSum(self,l,r):
		l,r=max(0,l),min(r,self.N-1)
		return __class__.op(self.InitialSegmentSum(r),__class__.inv(self.InitialSegmentSum(l-1)))if l<=r else 0
	def list(self):return[self.Get(i)for i in R(self.N)]
	def __str__(self):return rec_str(self.list())
	def Search(self,u):#Computing minimum of j such that InitialSegmentSum(j)>=u or j==N
		j=s=0
		n=copy(__class__.e)
		p=1<<17 #131072
		while p:
			k=j|p
			p>>=1
			if k<=self.N:
				n=__class__.op(n,self.Access(k))
				if n<u:s,j=n,k
				else:n=s
		return j

	#private:
	def Access(self,i):
		return self.F[i]if i in self.F else __class__.e

	def Replace(self,i,u):
		if u==__class__.e:del self.F[i]
		else:self.F[i]=u

R=range
I=input
N,Q=map(int,I().split())
S=[ord(c)-97 for c in I()]
L=26**3
T=[DynamicBIT(N-2)for s in R(L)]
def h(s):
	return s[0]*26*26+s[1]*26+s[2]
for i in R(N-2):
	T[h(S[i:i+3])].Set(i,[1,i+1])
for q in R(Q):
	t=I().split()
	if t[0]=='1':
		k,x=int(t[1])-1,ord(t[2])-97
		if S[k]!=x:
			for i in R(max(k-2,0),min(k+1,N-2)):T[h(S[i:i+3])].Set(i,[0,0])
			S[k]=x
			for i in R(max(k-2,0),min(k+1,N-2)):T[h(S[i:i+3])].Set(i,[1,i+1])
	else:
		l,r,a=int(t[1])-1,int(t[2])-1,h([ord(c)-97 for c in t[3]])
		if l<=r-2:
			c,s=T[a].IntervalSum(l,r-2)
			print(s-c*l)
		else:print(0)
0