結果

問題 No.3239 Omnibus
ユーザー 👑 p-adic
提出日時 2025-08-14 22:51:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 5,887 ms / 10,000 ms
コード長 2,102 bytes
コンパイル時間 321 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 276,048 KB
最終ジャッジ日時 2025-08-14 23:54:15
合計ジャッジ時間 116,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

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,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=self.Access(i,a)
			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=self.Access(k,n)
				if n<u:s,j=n,k
				else:n=s
		return j

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

	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