{"problem":{"name":"F. Substrings in a String","description":{"content":"Given a string _s_, process _q_ queries, each having one of the following forms: *   1 _i_ _c_ — Change the _i_\\-th character in the string to _c_. *   2 _l_ _r_ _y_ — Consider the substring of _s_ s","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF914F"},"statements":[{"statement_type":"Markdown","content":"Given a string _s_, process _q_ queries, each having one of the following forms:\n\n*   1 _i_ _c_ — Change the _i_\\-th character in the string to _c_.\n*   2 _l_ _r_ _y_ — Consider the substring of _s_ starting at position _l_ and ending at position _r_. Output the number of times _y_ occurs as a substring in it.\n\n## Input\n\nThe first line of the input contains the string _s_ (1 ≤ |_s_| ≤ 105) of lowercase English letters.\n\nThe second line contains an integer _q_ (1 ≤ _q_ ≤ 105) — the number of queries to process.\n\nThe next _q_ lines describe the queries and may have one of the following forms:\n\n*   1 _i_ _c_ (1 ≤ _i_ ≤ |_s_|)\n*   2 _l_ _r_ _y_ (1 ≤ _l_ ≤ _r_ ≤ |_s_|)\n\n_c_ is a lowercase English letter and _y_ is a non-empty string consisting of only lowercase English letters.\n\nThe sum of |_y_| over all queries of second type is at most 105.\n\nIt is guaranteed that there is at least one query of second type.\n\nAll strings are 1\\-indexed.\n\n|_s_| is the length of the string _s_.\n\n## Output\n\nFor each query of type 2, output the required answer in a separate line.\n\n[samples]\n\n## Note\n\nConsider the first sample case. Initially, the string _aba_ occurs 3 times in the range \\[1, 7\\]. Note that two occurrences may overlap.\n\nAfter the update, the string becomes _ababcbaba_ and now _aba_ occurs only once in the range \\[1, 7\\].","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一个字符串 $s$，处理 $q$ 个查询，每个查询具有以下形式之一：\n\n输入的第一行包含字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。\n\n第二行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——需要处理的查询数量。\n\n接下来的 $q$ 行描述查询，可能具有以下形式之一：\n\n$1\\ i\\ c$（$1 ≤ i ≤ |s|$）\n\n$2\\ l\\ r\\ y$（$1 ≤ l ≤ r ≤ |s|$）\n\n其中 $c$ 是一个小写英文字母，$y$ 是一个仅由小写英文字母组成的非空字符串。\n\n所有第二类查询中 $|y|$ 的总和不超过 $10^5$。\n\n保证至少存在一个第二类查询。\n\n所有字符串均为 $1$-索引。\n\n$|s|$ 表示字符串 $s$ 的长度。\n\n对于每个第二类查询，请在单独一行中输出所需答案。\n\n考虑第一个样例。初始时，字符串 _aba_ 在区间 $[1, 7]$ 中出现 $3$ 次。注意，两个出现可以重叠。\n\n更新后，字符串变为 _ababcbaba_，现在 _aba_ 在区间 $[1, 7]$ 中仅出现一次。\n\n## Input\n\n输入的第一行包含字符串 $s$（$1 ≤ |s| ≤ 10^5$），由小写英文字母组成。第二行包含一个整数 $q$（$1 ≤ q ≤ 10^5$）——需要处理的查询数量。接下来的 $q$ 行描述查询，可能具有以下形式之一： $1\\ i\\ c$（$1 ≤ i ≤ |s|$） $2\\ l\\ r\\ y$（$1 ≤ l ≤ r ≤ |s|$）其中 $c$ 是一个小写英文字母，$y$ 是一个仅由小写英文字母组成的非空字符串。所有第二类查询中 $|y|$ 的总和不超过 $10^5$。保证至少存在一个第二类查询。所有字符串均为 $1$-索引。$|s|$ 表示字符串 $s$ 的长度。\n\n## Output\n\n对于每个第二类查询，请在单独一行中输出所需答案。\n\n[samples]\n\n## Note\n\n考虑第一个样例。初始时，字符串 _aba_ 在区间 $[1, 7]$ 中出现 $3$ 次。注意，两个出现可以重叠。更新后，字符串变为 _ababcbaba_，现在 _aba_ 在区间 $[1, 7]$ 中仅出现一次。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ s \\in \\Sigma^* $ be a string of length $ n = |s| $, where $ \\Sigma $ is the set of lowercase English letters, and $ s $ is 1-indexed.\n- Let $ q \\in \\mathbb{N} $ be the number of queries.\n- Two types of queries:\n  1. **Update**: Replace the character at position $ c $ (1-indexed) with a new character (implicitly, the string $ s $ is modified).\n  2. **Query**: Given a non-empty pattern string $ y $, count the number of occurrences of $ y $ as a substring in the prefix $ s[1..7] $ (i.e., the first 7 characters of the current string $ s $).\n\n**Constraints:**\n\n- $ 1 \\leq n \\leq 10^5 $\n- $ 1 \\leq q \\leq 10^5 $\n- For each query of type 2, $ y \\in \\Sigma^+ $, and the total sum of $ |y| $ over all type-2 queries is $ \\leq 10^5 $\n- At least one query is of type 2.\n- All string indices are 1-based.\n\n**Objective:**\n\nFor each query of type 2, compute:\n\n$$\n\\left| \\left\\{ i \\in [1, 7 - |y| + 1] \\mid s[i..i + |y| - 1] = y \\right\\} \\right|\n$$\n\nThat is, the number of starting positions $ i $ in the range $ [1, 7 - |y| + 1] $ such that the substring of $ s $ from position $ i $ to $ i + |y| - 1 $ equals $ y $.\n\n**Note:** After each update query (type 1), the string $ s $ is modified in-place, and subsequent queries operate on the updated string.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF914F","tags":["bitmasks","brute force","data structures","string suffix structures","strings"],"sample_group":[["ababababa\n3\n2 1 7 aba\n1 5 c\n2 1 7 aba","3\n1"],["abcdcbc\n5\n2 1 7 bc\n1 4 b\n2 4 7 bc\n1 2 a\n2 1 4 aa","2\n2\n1"]],"created_at":"2026-03-03 11:00:39"}}