結果

問題 No.3239 Omnibus
ユーザー 👑 p-adic
提出日時 2025-08-14 21:23:30
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,765 bytes
コンパイル時間 694 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 431,908 KB
最終ジャッジ日時 2025-08-14 21:23:45
合計ジャッジ時間 13,811 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

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 DynamicSegmentTree:
	e=[0,0] #User's definition
	op=lambda x,y:[x[0]+y[0],x[1]+y[1]] #User's definition

	def __init__(self,N):
		self.N=N
		self.p=1
		while self.N>self.p:self.p<<=1
		self.T={}

	def copy(self):
		a=__class__(0)
		a.N=self.N
		a.p=self.p
		a.T=copy(self.T)
		return a

	def Set(self,i,u):
		assert 0<=i<self.N
		j=self.p|i
		self.Replace(j,u)
		j>>=1
		while j:
			self.Replace(j,__class__.op(self.Access(j<<1),self.Access((j<<1)|1)))
			j>>=1

	def Get(self,i):
		assert 0<=i<self.N
		return self.IntervalProduct(i,i)

	def IntervalProduct(self,l,r): #[l,r]
		l,r=max(0,l),min(r,self.N-1)
		assert l-1<=r
		l|=self.p
		r+=self.p+1
		a,b=copy(__class__.e),copy(__class__.e)
		while l<r:
			if l&1:a,l=__class__.op(a,self.Access(l)),l+1
			if r&1:b,r=__class__.op(self.Access(r-1),b),r-1
			l,r=l>>1,r>>1
		return __class__.op(a,b)

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

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

R=range
I=input
N,Q=map(int,I().split())
S=[ord(c)-97 for c in I()]
L=26**3
T=[DynamicSegmentTree(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].IntervalProduct(l,r-2)
			print(s-c*l)
		else:print(0)
0