#1179167 (PyPy3) No.3638 Itsuki

• 問題: No.3638 Itsuki
• ユーザー: 👑 loop0919
• 提出日時: 2026-08-25 19:17:02
• 言語: PyPy3 (7.3.17)
• 結果: TLE
• 実行時間: -
• コード長: 8,323 bytes
• コンパイル時間: 242 ms
• コンパイル使用メモリ: 95,468 KB
• 実行使用メモリ: 93,428 KB
• 最終ジャッジ日時: 2026-08-25 19:17:21
• 合計ジャッジ時間: 14,168 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

サブタスク	配点	結果
サンプル	0 %	AC * 2
小課題1	10 %	AC * 5
小課題2	50 %	AC * 5 TLE * 1
小課題3	40 %	AC * 17 TLE * 1
合計	10 点

ソースコード

import sys
from random import randrange

input = lambda: sys.stdin.readline().rstrip()


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")