CF827C DNA Evolution

众所周知，DNA链由核苷酸组成。共有四种类型的核苷酸，分别为“A”、“T”、“G”、“C”。一条 DNA 链是由核苷酸序列组成的。科学家们决定追踪一种稀有物种的进化，该物种最初的 DNA 链为字符串 $s$。 该物种的进化被描述为 DNA 链的一系列变化。每一次变化都意味着某个核苷酸发生变化，例如：DNA 链 “AAGC” 中，第二个核苷酸可以变为“T”，这样得到的新 DNA 链为“ATGC”。 科学家们已知，DNA 链的一些区段可能会受到未知感染的影响。他们可以用一个核苷酸序列来表示感染。科学家们关心是否存在被某些感染引起的变化。因而，他们有时希望知道某个感染对 DNA 某一段的影响值。该数值的计算方式如下： - 假设感染用字符串 $e$ 表示，科学家们关注的是 DNA 链从第 $l$ 位到第 $r$ 位（包含两端）这一段。 - 将无限重复的字符串 $e$ 形成 $eee\ldots$，然后截取一个前缀，使其长度等于 $r-l+1$，将该前缀依次对应写在字符串 $s$ 的第 $l$ 位到第 $r$ 位下面。 - 影响值指的是，$s$ 与下方所写字符相同的位置数量。 作为开发者的 Innokenty 也对生物信息学感兴趣，因此科学家们向他寻求帮助。但 Innokenty 忙于准备 VK Cup，于是他决定让参赛者来解决这个问题。请帮助科学家们吧！

第一行是字符串 $s$（$1 \leq |s| \leq 10^{5}$），表示最初的 DNA 链。它只包含大写英文字母“A”、“T”、“G”、“C”。 第二行是一个整数 $q$（$1 \leq q \leq 10^{5}$），表示事件的数量。 接下来有 $q$ 行，每行描述一个事件，格式如下二选一： - 1 x c，其中 $x$ 是整数（$1 \leq x \leq |s|$），$c$ 是字母“A”、“T”、“G”或“C”，表示 DNA 链的第 $x$ 位的核苷酸现在变成 $c$。 - 2 l r e，其中 $l, r$ 是整数（$1 \leq l \leq r \leq |s|$），$e$ 是只包含字母“A”、“T”、“G”、“C”的字符串（$1 \leq |e| \leq 10$），表示科学家关注感染 $e$ 对 DNA 链第 $l$ 位到第 $r$ 位的影响值。

对于每一个科学家的查询（第二种类型的查询），请在新的一行输出一个整数，表示该感染对指定区段 DNA 的影响值。

参考第一个样例。在第一次科学家查询时，所有字符都完全相同，所以答案为 $8$。第二次查询时，将字符串“TTTTT……”与“ TGCAT ”进行比较，有 $2$ 个位置相同。第三次查询，在 DNA 发生一次变化后，比对“ TATAT……”与 “TGTAT”，共有 $4$ 个位置相同。 由 ChatGPT 5 翻译