#1179010 (PyPy3) No.3638 Itsuki

• 問題: No.3638 Itsuki
• ユーザー: lif4635
• 提出日時: 2026-08-25 15:01:53
• 言語: PyPy3 (7.3.17)
• 結果: TLE
• 実行時間: -
• コード長: 24,723 bytes
• コンパイル時間: 252 ms
• コンパイル使用メモリ: 96,240 KB
• 実行使用メモリ: 94,256 KB
• 最終ジャッジ日時: 2026-08-25 15:02:05
• 合計ジャッジ時間: 11,329 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

# harurun's library（依存を含む貼り付け用コード）

# 依存: string/RollingHash.py
from time import time_ns
MOD = (1 << 61) - 1
MASK = MOD

def _string_rolling_hash_mul(left, right):
    value = left * right
    value = (value & MASK) + (value >> 61)
    return value - MOD if value >= MOD else value

def _string_rolling_hash_fma(left, right, add):
    value = left * right + add
    value = (value & MASK) + (value >> 61)
    return value - MOD if value >= MOD else value

def _string_rolling_hash_splitmix(value):
    value = value + 11400714819323198485 & (1 << 64) - 1
    value = (value ^ value >> 30) * 13787848793156543929 & (1 << 64) - 1
    value = (value ^ value >> 27) * 10723151780598845931 & (1 << 64) - 1
    return value ^ value >> 31
_string_rolling_hash_seed = time_ns() ^ id(object())
DEFAULT_BASE = _string_rolling_hash_splitmix(_string_rolling_hash_seed) % (MOD - (1 << 20)) + (1 << 20)
DEFAULT_BASE2 = _string_rolling_hash_splitmix(_string_rolling_hash_seed ^ 15111065706836454659) % (MOD - (1 << 20)) + (1 << 20)
if DEFAULT_BASE2 == DEFAULT_BASE:
    DEFAULT_BASE2 -= 1

def _string_rolling_hash_symbol_value(symbol):
    if isinstance(symbol, str):
        symbol = ord(symbol)
    return int(symbol) % MOD

def _string_rolling_hash_component_hash(sequence, base):
    value = 0
    for symbol in sequence:
        value = _string_rolling_hash_fma(value, base, _string_rolling_hash_symbol_value(symbol))
    return value

def hash_sequence(sequence, base=DEFAULT_BASE, base2=None):
    first = _string_rolling_hash_component_hash(sequence, base)
    if base2 is None:
        return first
    return (first, _string_rolling_hash_component_hash(sequence, base2))

def _string_rolling_hash_combine_hash(left, right, right_power):
    if isinstance(left, tuple):
        return tuple((_string_rolling_hash_fma(a, p, b) for (a, b, p) in zip(left, right, right_power)))
    return _string_rolling_hash_fma(left, right_power, right)

def _string_rolling_hash_multiply_hash(left, right):
    if isinstance(left, tuple):
        return tuple((_string_rolling_hash_mul(a, b) for (a, b) in zip(left, right)))
    return _string_rolling_hash_mul(left, right)

class HashString:
    __slots__ = ('hash', 'reverse_hash', 'power', 'length', 'bases')

    def __init__(self, value, power, length, bases, reverse_value=None):
        self.hash = value
        self.reverse_hash = reverse_value
        self.power = power
        self.length = length
        self.bases = bases

    @classmethod
    def empty(cls, bases=(DEFAULT_BASE,), reversible=False):
        if len(bases) == 1:
            return cls(0, 1, 0, bases, 0 if reversible else None)
        zero = (0,) * len(bases)
        one = (1,) * len(bases)
        return cls(zero, one, 0, bases, zero if reversible else None)

    @classmethod
    def from_sequence(cls, sequence, base=DEFAULT_BASE, base2=None, reversible=False):
        rolling = RollingHash(sequence, base, base2, reversible)
        return rolling.get_value(0, len(rolling))

    def __len__(self):
        return self.length

    def __eq__(self, other):
        return isinstance(other, HashString) and self.length == other.length and (self.bases == other.bases) and (self.hash == other.hash)

    def __hash__(self):
        return hash((self.length, self.bases, self.hash))

    def __add__(self, other):
        if not isinstance(other, HashString) or self.bases != other.bases:
            return NotImplemented
        value = _string_rolling_hash_combine_hash(self.hash, other.hash, other.power)
        power = _string_rolling_hash_multiply_hash(self.power, other.power)
        if self.reverse_hash is None or other.reverse_hash is None:
            reverse_value = None
        else:
            reverse_value = _string_rolling_hash_combine_hash(other.reverse_hash, self.reverse_hash, self.power)
        return HashString(value, power, self.length + other.length, self.bases, reverse_value)
    concat = __add__

    def reversed(self):
        if self.reverse_hash is None:
            raise ValueError('reverse hash was not built')
        return HashString(self.reverse_hash, self.power, self.length, self.bases, self.hash)
    reverse = reversed

    def is_palindrome(self):
        return self.reverse_hash is not None and self.hash == self.reverse_hash

    def repeat(self, count):
        assert count >= 0
        result = HashString.empty(self.bases, self.reverse_hash is not None)
        block = self
        while count:
            if count & 1:
                result = result + block
            count >>= 1
            if count:
                block = block + block
        return result

    def __mul__(self, count):
        return self.repeat(count)
    __rmul__ = __mul__

    def remove_prefix(self, prefix):
        assert self.bases == prefix.bases and prefix.length <= self.length
        remaining = self.length - prefix.length
        if len(self.bases) == 1:
            power = pow(self.bases[0], remaining, MOD)
            value = self.hash - _string_rolling_hash_mul(prefix.hash, power)
            if value < 0:
                value += MOD
        else:
            power = tuple((pow(base, remaining, MOD) for base in self.bases))
            value = []
            for (full, part, component_power) in zip(self.hash, prefix.hash, power):
                current = full - _string_rolling_hash_mul(part, component_power)
                value.append(current + MOD if current < 0 else current)
            value = tuple(value)
        return HashString(value, power, remaining, self.bases)

class RollingHash:
    __slots__ = ('data', 'n', 'base', 'base2', 'prefix', 'power', 'prefix2', 'power2', 'reverse_prefix', 'reverse_prefix2', 'reversible')

    def __init__(self, sequence=(), base=DEFAULT_BASE, base2=None, reversible=False):
        if not hasattr(sequence, '__len__'):
            sequence = list(sequence)
        self.data = sequence
        self.n = len(sequence)
        self.base = base
        self.base2 = base2
        self.reversible = reversible
        prefix = [0] * (self.n + 1)
        power = [1] * (self.n + 1)
        value = 0
        base_power = 1
        for (i, symbol) in enumerate(sequence):
            value = _string_rolling_hash_fma(value, base, _string_rolling_hash_symbol_value(symbol))
            base_power = _string_rolling_hash_mul(base_power, base)
            prefix[i + 1] = value
            power[i + 1] = base_power
        self.prefix = prefix
        self.power = power
        if base2 is None:
            self.prefix2 = None
            self.power2 = None
        else:
            prefix2 = [0] * (self.n + 1)
            power2 = [1] * (self.n + 1)
            value = 0
            base_power = 1
            for (i, symbol) in enumerate(sequence):
                value = _string_rolling_hash_fma(value, base2, _string_rolling_hash_symbol_value(symbol))
                base_power = _string_rolling_hash_mul(base_power, base2)
                prefix2[i + 1] = value
                power2[i + 1] = base_power
            self.prefix2 = prefix2
            self.power2 = power2
        if reversible:
            reverse_prefix = [0] * (self.n + 1)
            value = 0
            for i in range(self.n):
                value = _string_rolling_hash_fma(value, base, _string_rolling_hash_symbol_value(sequence[self.n - 1 - i]))
                reverse_prefix[i + 1] = value
            self.reverse_prefix = reverse_prefix
            if base2 is None:
                self.reverse_prefix2 = None
            else:
                reverse_prefix2 = [0] * (self.n + 1)
                value = 0
                for i in range(self.n):
                    value = _string_rolling_hash_fma(value, base2, _string_rolling_hash_symbol_value(sequence[self.n - 1 - i]))
                    reverse_prefix2[i + 1] = value
                self.reverse_prefix2 = reverse_prefix2
        else:
            self.reverse_prefix = None
            self.reverse_prefix2 = None

    def __len__(self):
        return self.n

    @property
    def bases(self):
        return (self.base,) if self.base2 is None else (self.base, self.base2)

    def _get_component(self, prefix, power, left, right):
        value = prefix[right] - _string_rolling_hash_mul(prefix[left], power[right - left])
        return value + MOD if value < 0 else value

    def get(self, left=0, right=None):
        if right is None:
            right = self.n
        assert 0 <= left <= right <= self.n
        first = self._get_component(self.prefix, self.power, left, right)
        if self.base2 is None:
            return first
        return (first, self._get_component(self.prefix2, self.power2, left, right))
    query = get

    def reverse_get(self, left=0, right=None):
        if right is None:
            right = self.n
        if self.reverse_prefix is None:
            raise ValueError('reverse hash was not built')
        assert 0 <= left <= right <= self.n
        reverse_left = self.n - right
        reverse_right = self.n - left
        first = self._get_component(self.reverse_prefix, self.power, reverse_left, reverse_right)
        if self.base2 is None:
            return first
        return (first, self._get_component(self.reverse_prefix2, self.power2, reverse_left, reverse_right))

    def get_value(self, left=0, right=None):
        if right is None:
            right = self.n
        length = right - left
        if self.base2 is None:
            power = self.power[length]
        else:
            power = (self.power[length], self.power2[length])
        reverse_value = self.reverse_get(left, right) if self.reversible else None
        return HashString(self.get(left, right), power, length, self.bases, reverse_value)
    to_hash_string = get_value

    def same(self, left1, right1, other, left2, right2):
        return right1 - left1 == right2 - left2 and self.bases == other.bases and (self.get(left1, right1) == other.get(left2, right2))

    def lcp(self, other, left1=0, right1=None, left2=0, right2=None):
        if right1 is None:
            right1 = self.n
        if right2 is None:
            right2 = other.n
        assert self.bases == other.bases
        length = min(right1 - left1, right2 - left2)
        low = 0
        high = length + 1
        while high - low > 1:
            middle = low + high >> 1
            if self.get(left1, left1 + middle) == other.get(left2, left2 + middle):
                low = middle
            else:
                high = middle
        return low
    LCP = lcp

    def compare(self, other, left1=0, right1=None, left2=0, right2=None):
        if right1 is None:
            right1 = self.n
        if right2 is None:
            right2 = other.n
        common = self.lcp(other, left1, right1, left2, right2)
        end1 = left1 + common == right1
        end2 = left2 + common == right2
        if end1:
            return 0 if end2 else -1
        if end2:
            return 1
        return -1 if self.data[left1 + common] < other.data[left2 + common] else 1
    strcmp = compare

    def find(self, pattern, lower=0):
        if isinstance(pattern, RollingHash):
            target = pattern.get()
            length = pattern.n
            assert self.bases == pattern.bases
        else:
            length = len(pattern)
            target = hash_sequence(pattern, self.base, self.base2)
        for i in range(lower, self.n - length + 1):
            if self.get(i, i + length) == target:
                return i
        return -1

    def append(self, symbol):
        if self.reversible:
            raise ValueError('incremental append is unavailable with reverse hash')
        if not isinstance(self.data, list):
            self.data = list(self.data)
        self.data.append(symbol)
        value = _string_rolling_hash_symbol_value(symbol)
        self.prefix.append(_string_rolling_hash_fma(self.prefix[-1], self.base, value))
        self.power.append(_string_rolling_hash_mul(self.power[-1], self.base))
        if self.base2 is not None:
            self.prefix2.append(_string_rolling_hash_fma(self.prefix2[-1], self.base2, value))
            self.power2.append(_string_rolling_hash_mul(self.power2[-1], self.base2))
        self.n += 1

    def extend(self, sequence):
        for symbol in sequence:
            self.append(symbol)
        return self
    connect = extend

    def __getitem__(self, index):
        if isinstance(index, slice):
            (left, right, step) = index.indices(self.n)
            if step != 1:
                return self.data[index]
            return RollingHashView(self, left, right)
        return self.data[index]

class DoubleRollingHash(RollingHash):
    __slots__ = ()

    def __init__(self, sequence=(), bases=None, reversible=False):
        if bases is None:
            bases = (DEFAULT_BASE, DEFAULT_BASE2)
        super().__init__(sequence, bases[0], bases[1], reversible)

class ReversibleRollingHash(RollingHash):
    __slots__ = ()

    def __init__(self, sequence=(), base=DEFAULT_BASE, base2=None):
        super().__init__(sequence, base, base2, True)

class RollingHashView:
    __slots__ = ('base', 'left', 'right', 'l', 'r')

    def __init__(self, base, left, right):
        self.base = base
        self.left = left
        self.right = right
        self.l = left
        self.r = right

    def __len__(self):
        return self.right - self.left

    @property
    def hash(self):
        return self.base.get(self.left, self.right)

    def to_hash_string(self):
        return self.base.get_value(self.left, self.right)

    def lcp(self, other):
        return self.base.lcp(other.base, self.left, self.right, other.left, other.right)
    LCP = lcp

    def compare(self, other):
        return self.base.compare(other.base, self.left, self.right, other.left, other.right)
    cmp = compare

    def is_palindrome(self):
        return self.to_hash_string().is_palindrome()

    def reversed(self):
        return self.to_hash_string().reversed()

    def __getitem__(self, index):
        if isinstance(index, slice):
            (left, right, step) = index.indices(len(self))
            if step != 1:
                return self.base.data[self.left:self.right][index]
            return RollingHashView(self.base, self.left + left, self.left + right)
        if index < 0:
            index += len(self)
        if not 0 <= index < len(self):
            raise IndexError('rolling hash view index out of range')
        return self.base.data[self.left + index]

    def __eq__(self, other):
        return isinstance(other, RollingHashView) and len(self) == len(other) and (self.base.bases == other.base.bases) and (self.hash == other.hash)

    def __lt__(self, other):
        return self.compare(other) < 0

    def __str__(self):
        return str(self.base.data[self.left:self.right])

# 本体
class DynamicRollingHash:
    __slots__ = ('n', 'size', 'base', 'data', 'power', 'forward', 'reverse', 'length')

    def __init__(self, sequence=(), base=DEFAULT_BASE):
        sequence = list(sequence)
        n = len(sequence)
        size = 1
        while size < n:
            size <<= 1
        power = [1] * (n + 1)
        for i in range(n):
            power[i + 1] = _string_rolling_hash_mul(power[i], base)
        forward = [0] * (size << 1)
        reverse = [0] * (size << 1)
        length = [0] * (size << 1)
        for (i, symbol) in enumerate(sequence):
            value = _string_rolling_hash_symbol_value(symbol)
            position = size + i
            forward[position] = reverse[position] = value
            length[position] = 1
        for position in range(size - 1, 0, -1):
            left = position << 1
            right = left | 1
            left_length = length[left]
            right_length = length[right]
            length[position] = left_length + right_length
            forward[position] = _string_rolling_hash_fma(forward[left], power[right_length], forward[right])
            reverse[position] = _string_rolling_hash_fma(reverse[right], power[left_length], reverse[left])
        self.n = n
        self.size = size
        self.base = base
        self.data = sequence
        self.power = power
        self.forward = forward
        self.reverse = reverse
        self.length = length

    def __len__(self):
        return self.n

    def update(self, index, value):
        assert 0 <= index < self.n
        self.data[index] = value
        position = self.size + index
        value = _string_rolling_hash_symbol_value(value)
        self.forward[position] = self.reverse[position] = value
        position >>= 1
        while position:
            left = position << 1
            right = left | 1
            left_length = self.length[left]
            right_length = self.length[right]
            self.forward[position] = _string_rolling_hash_fma(self.forward[left], self.power[right_length], self.forward[right])
            self.reverse[position] = _string_rolling_hash_fma(self.reverse[right], self.power[left_length], self.reverse[left])
            position >>= 1
    set = update

    def _query(self, left, right):
        assert 0 <= left <= right <= self.n
        left += self.size
        right += self.size
        left_forward = left_reverse = left_length = 0
        right_forward = right_reverse = right_length = 0
        while left < right:
            if left & 1:
                node_length = self.length[left]
                left_forward = _string_rolling_hash_fma(left_forward, self.power[node_length], self.forward[left])
                left_reverse = _string_rolling_hash_fma(self.reverse[left], self.power[left_length], left_reverse)
                left_length += node_length
                left += 1
            if right & 1:
                right -= 1
                node_length = self.length[right]
                right_forward = _string_rolling_hash_fma(self.forward[right], self.power[right_length], right_forward)
                right_reverse = _string_rolling_hash_fma(right_reverse, self.power[node_length], self.reverse[right])
                right_length += node_length
            left >>= 1
            right >>= 1
        forward = _string_rolling_hash_fma(left_forward, self.power[right_length], right_forward)
        reverse = _string_rolling_hash_fma(right_reverse, self.power[left_length], left_reverse)
        return (forward, reverse, left_length + right_length)

    def get(self, left=0, right=None):
        if right is None:
            right = self.n
        return self._query(left, right)[0]
    query = get

    def reverse_get(self, left=0, right=None):
        if right is None:
            right = self.n
        return self._query(left, right)[1]

    def get_value(self, left=0, right=None):
        if right is None:
            right = self.n
        (forward, reverse, length) = self._query(left, right)
        return HashString(forward, self.power[length], length, (self.base,), reverse)

    def same(self, left1, right1, left2, right2):
        return right1 - left1 == right2 - left2 and self.get(left1, right1) == self.get(left2, right2)

    def is_palindrome(self, left=0, right=None):
        if right is None:
            right = self.n
        (forward, reverse, _) = self._query(left, right)
        return forward == reverse

    def lcp(self, left1, right1, left2, right2):
        length = min(right1 - left1, right2 - left2)
        low = 0
        high = length + 1
        while high - low > 1:
            middle = low + high >> 1
            if self.get(left1, left1 + middle) == self.get(left2, left2 + middle):
                low = middle
            else:
                high = middle
        return low

    def __getitem__(self, index):
        return self.data[index]



# input
import sys
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : map(int, input().split())
LI = lambda : [int(a) for a in input().split()]
SI = lambda : input().rstrip()
LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)]
LSI = lambda n : [input().rstrip() for _ in range(n)]
MI_1 = lambda : map(lambda x:int(x)-1, input().split())
LI_1 = lambda : [int(a)-1 for a in input().split()]

mod = 998244353
inf = 1001001001001001001
ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97
ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97
yes = lambda : print("Yes")
no = lambda : print("No")
yn = lambda flag : print("Yes" if flag else "No")

prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)
alplow = "abcdefghijklmnopqrstuvwxyz"
alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]
prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
sys.set_int_max_str_digits(0)
# sys.setrecursionlimit(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')

from collections import defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
DD = defaultdict
BSL = bisect_left
BSR = bisect_right

class SegTree:
    __slots__ = ["n", "size", "op", "e", "data"]
    
    def __init__(self, op, e, lst):
        self.n = len(lst)
        self.size = 1 << (self.n - 1).bit_length()
        self.op = op
        self.e = e
        self.data = [e] * (2 * self.size)
        for i in range(self.n):
            self.data[self.size + i] = lst[i]
        for i in range(self.size - 1, 0, -1):
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
    
    def get(self, i):
        return self.data[self.size+i]
    
    def add(self, i, x):
        i += self.size
        self.data[i] = self.op(x, self.data[i])
        while i > 1:
            i >>= 1
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
    
    def set(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 1:
            i >>= 1
            self.data[i] = self.op(self.data[2*i], self.data[2*i+1])
    
    def prod(self, l, r):
        if r <= l:
            return self.e
        lres = self.e
        rres = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                lres = self.op(lres, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                rres = self.op(self.data[r], rres)
            l >>= 1
            r >>= 1
        return self.op(lres, rres)
    
    def all_prod(self):
        return self.data[1]
    
    def max_right(self, l, g):
        assert 0<=l and l<=self.n
        assert g(self.e)
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while 1:
            while l&1 == 0:
                l >>= 1
            if not(g(self.op(sm, self.data[l]))):
                while l < self.size:
                    l = 2*l
                    nsm = self.op(sm, self.data[l])
                    if g(nsm):
                        sm = nsm
                        l += 1
                return l-self.size
            sm = self.op(sm, self.data[l])
            l += 1
            if (l&-l) == l: break
        return self.n
    
    def min_left(self, r, g):
        if r == -1: r = self.n
        assert 0<=r and r<=self.n
        assert g(self.e)
        if r == 0: return 0
        r += self.size
        sm = self.e
        while 1:
            r -= 1
            while (r>1 and r&1):
                r >>= 1
            if not(g(self.op(self.data[r], sm))):
                while r < self.size:
                    r = 2*r+1
                    nsm = self.op(self.data[r], sm)
                    if g(nsm):
                        sm = nsm
                        r -= 1
                return r + 1 -self.size
            sm = self.op(self.data[r], sm)
            if (r&-r) == r: break
        return 0
    
    def __str__(self):
        return str(self.data[self.size:self.size+self.n])
    
n, q = MI()
s = SI()




r = DynamicRollingHash(s)

for i in range(q):
    qry = list(input().split())
    if qry[0] == "1":
        _, i, c = qry
        i = int(i) - 1 
        r.update(i, c)
    else:
        _, t = qry
        # r2 = DynamicRollingHash(t)
        p = hash_sequence(t, r.base)
        # print(p)
        for i in range(len(s) - len(t) + 1):
            q = r.get(i, i+len(t))
            # print(q)
            if p == q:
                print("Yes")
                break
        else:
            print("No")