結果
| 問題 | No.3638 Itsuki |
| コンテスト | |
| ユーザー |
👑  loop0919
|
| 提出日時 | 2026-08-25 19:15:42 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,265 bytes |
| 記録 | |
| コンパイル時間 | 242 ms |
| コンパイル使用メモリ | 95,844 KB |
| 実行使用メモリ | 94,136 KB |
| 最終ジャッジ日時 | 2026-08-25 19:15:58 |
| 合計ジャッジ時間 | 14,753 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サンプル | 0 % | AC * 2 |
| 小課題1 | 10 % | AC * 5 |
| 小課題2 | 50 % | AC * 5 TLE * 1 |
| 小課題3 | 40 % | AC * 17 TLE * 1 |
| 合計 | 10 点 |
ソースコード
from random import randrange
class segtree:
n = 1
size = 1
log = 2
d = [0]
op = None
e = 10**15
def __init__(self, V, OP, E):
self.n = len(V)
self.op = OP
self.e = E
self.log = (self.n - 1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2 * self.size)]
d = self.d
for i in range(self.n):
d[self.size + i] = V[i]
op = self.op
for i in range(self.size - 1, 0, -1):
d[i] = op(d[2 * i], d[2 * i + 1])
def set(self, p, x):
assert 0 <= p and p < self.n
d = self.d
op = self.op
p += self.size
d[p] = x
for i in range(1, self.log + 1):
k = p >> i
d[k] = op(d[2 * k], d[2 * k + 1])
def get(self, p):
assert 0 <= p and p < self.n
return self.d[p + self.size]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
d = self.d
op = self.op
sml = self.e
smr = self.e
l += self.size
r += self.size
while l < r:
if l & 1:
sml = op(sml, d[l])
l += 1
if r & 1:
smr = op(d[r - 1], smr)
r -= 1
l >>= 1
r >>= 1
return op(sml, smr)
def all_prod(self):
return self.d[1]
def max_right(self, l, f):
assert 0 <= l and l <= self.n
assert f(self.e)
if l == self.n:
return self.n
d = self.d
op = self.op
size = self.size
l += size
sm = self.e
while 1:
while l % 2 == 0:
l >>= 1
if not (f(op(sm, d[l]))):
while l < size:
l = 2 * l
if f(op(sm, d[l])):
sm = op(sm, d[l])
l += 1
return l - size
sm = op(sm, d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, f):
assert 0 <= r and r <= self.n
assert f(self.e)
if r == 0:
return 0
d = self.d
op = self.op
size = self.size
r += size
sm = self.e
while 1:
r -= 1
while r > 1 and (r % 2):
r >>= 1
if not (f(op(d[r], sm))):
while r < size:
r = 2 * r + 1
if f(op(d[r], sm)):
sm = op(d[r], sm)
r -= 1
return r + 1 - size
sm = op(d[r], sm)
if (r & -r) == r:
break
return 0
def update(self, k):
self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
def __str__(self):
return str([self.get(i) for i in range(self.n)])
MASK30 = (1 << 30) - 1
MASK31 = (1 << 31) - 1
MASK61 = (1 << 61) - 1
MASK30 = (1 << 30) - 1
MASK31 = (1 << 31) - 1
MASK61 = (1 << 61) - 1
class RollingHash:
"""\
ローリングハッシュ
O(1) で文字列区間の一致判定を行うことができる
Usage::
rh = RollingHash("ababcccba", 65537)
print(rh.get(0, 2) == rh.get(2, 4))
# => True
print(rh.get(0, 3) == rh.get(1, 4))
# => False
"""
_list: list[int]
_N: int
_base: int
_table: list[int]
_inv: list[int]
def __init__(self, S: str | list[int], base: int):
"""\
法 2**61 - 1, 基数base でローリングハッシュを作成する
base はランダム値を使うと、敵対的なケースにも強くなる
"""
if isinstance(S, str):
self._list = [ord(s) for s in S]
else:
self._list = S
self._N = len(self._list)
self._base = base
self._build()
def _build(self) -> None:
"""ハッシュテーブルを構築する"""
self._table = [0] * (self._N + 1)
self._inv = [1] * (self._N + 1)
pow_base, inv_base = 1, self._pow(self._base, MASK61 - 2)
for i in range(self._N):
v = self._list[i]
pow_base = self._mul(pow_base, self._base)
self._table[i + 1] = (self._table[i] + self._mul(v, pow_base)) % MASK61
self._inv[i + 1] = self._mul(self._inv[i], inv_base)
def _mul(self, x: int, y: int) -> int:
x_low, x_high = x & MASK31, x >> 31
y_low, y_high = y & MASK31, y >> 31
mid = x_high * y_low + x_low * y_high
mid_low, mid_high = mid & MASK30, mid >> 30
ans = (x_high * y_high * 2) + ((mid_low << 31) + mid_high) + (x_low * y_low)
ans %= MASK61
return ans
def _pow(self, n: int, power: int):
ans = 1
for i in range(61, -1, -1):
ans = self._mul(ans, ans)
if (power >> i) & 1 == 1:
ans = self._mul(ans, n)
return ans
def get(self, l: int, r: int) -> int:
assert 0 <= l < r <= self._N
x = self._table[r] - self._table[l]
if x < 0:
x += MASK61
return self._mul(x, self._inv[l])
class RollingHashSegTree:
"""\
ローリングハッシュ
O(log N) で文字の変更 / 文字列区間の一致判定を行うことができる
"""
_list: list[int]
_N: int
_base: int
_table: segtree
_inv: list[int]
_pow_base: list[int]
def __init__(self, S: str | list[int], base: int):
"""\
法 2**61 - 1, 基数base でローリングハッシュを作成する
base はランダム値を使うと、敵対的なケースにも強くなる
"""
if isinstance(S, str):
self._list = [ord(s) for s in S]
else:
self._list = S
self._N = len(self._list)
self._base = base
self._build()
def _build(self) -> None:
"""ハッシュテーブルを構築する"""
self._table = segtree([0] * self._N, lambda x, y: (x + y) % MASK61, 0)
self._inv = [1] * (self._N + 1)
self._pow_base = [1] * (self._N + 1)
inv_base = self._pow(self._base, MASK61 - 2)
for i in range(self._N):
v = self._list[i]
self._pow_base[i + 1] = self._mul(self._pow_base[i], self._base)
self._table.set(i, self._mul(v, self._pow_base[i + 1]))
self._inv[i + 1] = self._mul(self._inv[i], inv_base)
def _mul(self, x: int, y: int) -> int:
x_low, x_high = x & MASK31, x >> 31
y_low, y_high = y & MASK31, y >> 31
mid = x_high * y_low + x_low * y_high
mid_low, mid_high = mid & MASK30, mid >> 30
ans = (x_high * y_high * 2) + ((mid_low << 31) + mid_high) + (x_low * y_low)
ans %= MASK61
return ans
def _pow(self, n: int, power: int):
ans = 1
for i in range(61, -1, -1):
ans = self._mul(ans, ans)
if (power >> i) & 1 == 1:
ans = self._mul(ans, n)
return ans
def set(self, p: int, x: str | int):
"""`S[p]` を x に更新する"""
assert 0 <= p < self._N
assert isinstance(x, int) or (isinstance(x, str) and len(x) == 1)
if isinstance(x, int):
v = x
else:
v = ord(x)
self._table.set(p, self._mul(v, self._pow_base[p + 1]))
def get(self, l: int, r: int) -> int:
"""`S[l:r]` のハッシュ値を取得する"""
assert 0 <= l < r <= self._N
x = self._table.prod(l, r)
return self._mul(x, self._inv[l])
BASE = randrange(2, MASK61)
N, Q = [int(s) for s in input().split()]
S = input()
rolling = RollingHashSegTree(S, BASE)
for _ in range(Q):
cmd, *query = input().split()
cmd = int(cmd)
if cmd == 1:
i, c = query
i = int(i) - 1
rolling.set(i, c)
else:
T = query[0]
M = len(T)
hash_t = RollingHash(T, BASE).get(0, M)
for i in range(N - M + 1):
if hash_t == rolling.get(i, i + M):
print("Yes")
break
else:
print("No")