結果
| 問題 |
No.3239 Omnibus
|
| ユーザー |
 ゼット
|
| 提出日時 | 2025-08-15 23:16:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,198 bytes |
| コンパイル時間 | 334 ms |
| コンパイル使用メモリ | 82,604 KB |
| 実行使用メモリ | 209,156 KB |
| 最終ジャッジ日時 | 2025-08-15 23:19:57 |
| 合計ジャッジ時間 | 193,243 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 31 |
ソースコード
from typing import Callable, Optional, TypeVar, Generic
_S = TypeVar('_S')
class DynamicSegTree(Generic[_S]):
class Node:
def __init__(self, index: int, value: _S):
self.index = index
self.value = value
self.product = value
self.left: Optional['DynamicSegTree.Node'] = None
self.right: Optional['DynamicSegTree.Node'] = None
def update(self, op: Callable[[_S, _S], _S], e: _S):
left_prod = self.left.product if self.left else e
right_prod = self.right.product if self.right else e
self.product = op(op(left_prod, self.value), right_prod)
def __init__(self, n: int, op: Callable[[_S, _S], _S], e: _S):
self.n = n
self.op = op
self.e = e
self.root: Optional[DynamicSegTree.Node] = None
def set(self, p: int, x: _S):
assert 0 <= p < self.n
self.root = self._set(self.root, 0, self.n, p, x)
def _set(self, t: Optional['DynamicSegTree.Node'], a: int, b: int, p: int, x: _S):
if t is None:
return self.Node(p, x)
if t.index == p:
t.value = x
t.update(self.op, self.e)
return t
c = (a + b) >> 1
if p < c:
if t.index < p:
t.index, p = p, t.index
t.value, x = x, t.value
t.left = self._set(t.left, a, c, p, x)
else:
if p < t.index:
t.index, p = p, t.index
t.value, x = x, t.value
t.right = self._set(t.right, c, b, p, x)
t.update(self.op, self.e)
return t
def get(self, p: int) -> _S:
assert 0 <= p < self.n
return self._get(self.root, 0, self.n, p)
def _get(self, t: Optional['DynamicSegTree.Node'], a: int, b: int, p: int) -> _S:
if t is None:
return self.e
if t.index == p:
return t.value
c = (a + b) >> 1
return self._get(t.left, a, c, p) if p < c else self._get(t.right, c, b, p)
def prod(self, l: int, r: int) -> _S:
assert 0 <= l <= r <= self.n
return self._prod(self.root, 0, self.n, l, r)
def _prod(self, t: Optional['DynamicSegTree.Node'], a: int, b: int, l: int, r: int) -> _S:
if t is None or b <= l or r <= a:
return self.e
if l <= a and b <= r:
return t.product
c = (a + b) >> 1
res = self._prod(t.left, a, c, l, r)
if l <= t.index < r:
res = self.op(res, t.value)
return self.op(res, self._prod(t.right, c, b, l, r))
def all_prod(self) -> _S:
return self.root.product if self.root else self.e
def reset(self, l: int, r: int):
assert 0 <= l <= r <= self.n
self.root = self._reset(self.root, 0, self.n, l, r)
def _reset(self, t: Optional['DynamicSegTree.Node'], a: int, b: int, l: int, r: int) -> Optional['DynamicSegTree.Node']:
if t is None or b <= l or r <= a:
return t
if l <= a and b <= r:
return None
c = (a + b) >> 1
t.left = self._reset(t.left, a, c, l, r)
t.right = self._reset(t.right, c, b, l, r)
t.update(self.op, self.e)
return t
def max_right(self, l: int, f: Callable[[_S], bool]) -> int:
assert 0 <= l <= self.n
prod = self.e
assert f(prod)
return self._max_right(self.root, 0, self.n, l, f, prod)
def _max_right(self, t: Optional['DynamicSegTree.Node'], a: int, b: int, l: int, f: Callable[[_S], bool], prod: _S) -> int:
if t is None or b <= l:
return self.n
if f(self.op(prod, t.product)):
prod = self.op(prod, t.product)
return self.n
c = (a + b) >> 1
res = self._max_right(t.left, a, c, l, f, prod)
if res != self.n:
return res
if l <= t.index:
prod = self.op(prod, t.value)
if not f(prod):
return t.index
return self._max_right(t.right, c, b, l, f, prod)
def min_left(self, r: int, f: Callable[[_S], bool]) -> int:
assert 0 <= r <= self.n
prod = self.e
assert f(prod)
return self._min_left(self.root, 0, self.n, r, f, prod)
def _min_left(self, t: Optional['DynamicSegTree.Node'], a: int, b: int, r: int, f: Callable[[_S], bool], prod: _S) -> int:
if t is None or r <= a:
return 0
if f(self.op(t.product, prod)):
prod = self.op(t.product, prod)
return 0
c = (a + b) >> 1
res = self._min_left(t.right, c, b, r, f, prod)
if res != 0:
return res
if t.index < r:
prod = self.op(t.value, prod)
if not f(prod):
return t.index + 1
return self._min_left(t.left, a, c, r, f, prod)
def op(l,r):
l1 = l
r1 = r
return l1+r1
E = (0)
Z=DynamicSegTree(10**9+2,op,E)
N,Q=map(int,input().split())
h=[0]*N
S=input()
for i in range(N):
h[i]=S[i]
Z1=[DynamicSegTree(10**9+2,op,E) for i in range(26**3)]
Z2=[DynamicSegTree(10**9+2,op,E) for i in range(26**3)]
for i in range(N-2):
x=ord(S[i])-ord('a')
y=ord(S[i+1])-ord('a')
z=ord(S[i+2])-ord('a')
c=x*26**2+y*26+z
Z1[c].set(i,1)
Z2[c].set(i,i)
S=h[:]
for _ in range(Q):
t,*A=input().split()
if t=='1':
k,x=A[:]
e=x
k=int(k)-1
for i in range(k-2,k+1):
if i<0:
continue
if i>=N-2:
continue
x=ord(S[i])-ord('a')
y=ord(S[i+1])-ord('a')
z=ord(S[i+2])-ord('a')
c=x*26**2+y*26+z
Z1[c].set(i,0)
Z2[c].set(i,0)
S[k]=e
for i in range(k-2,k+1):
if i<0:
continue
if i>=N-2:
continue
x=ord(S[i])-ord('a')
y=ord(S[i+1])-ord('a')
z=ord(S[i+2])-ord('a')
c=x*26**2+y*26+z
Z1[c].set(i,i)
Z2[c].set(i,i)
else:
l,r,a=A[:]
l=int(l)-1
r=int(r)-1
if r-l+1<3:
print(0)
continue
x=ord(a[0])-ord('a')
y=ord(a[1])-ord('a')
z=ord(a[2])-ord('a')
c=x*26**2+y*26+z
score=Z2[c].prod(l,r-1)
count=Z1[c].prod(l,r-1)
result=score-(l-1)*count
print(result)