← 返回题目列表

Codeforces · 827/C

C. DNA 进化

中文机器翻译题面 查看原题

每个人都知道 DNA 链由核苷酸组成。核苷酸有四种类型:“A”、“T”、“G”、“C”。 DNA 链是核苷酸序列。科学家们决定追踪一种稀有物种的进化,该物种的 DNA 链最初是 string s。

物种的进化被描述为 DNA 的一系列变化。每个变化都是某个核苷酸的变化,例如,DNA链“AAGC”中可能发生以下变化:第二个核苷酸可以变为“T”,从而得到的DNA链是“ATGC”。

科学家们知道 DNA 链的某些片段可能会受到某些未知感染的影响。它们可以将感染表示为核苷酸序列。科学家们对某些感染是否会引起任何变化感兴趣。因此,他们有时想知道某些感染对 DNA 某些片段的影响价值。该值计算如下:

- 让感染表示为字符串 e,并让科学家对从位置 l 到位置 r(包括这两个位置)的 DNA 链片段感兴趣。
- 字符串 eee... 的前缀(即由字符串 e 的无限多次重复组成的字符串)写在字符串 s 下,从位置 l 到位置 r(含)。
- 影响值是字符串 s 中的字母与其下方的字母重合的位置数。

作为一名开发人员,Innokenty 对生物信息学也很感兴趣,因此科学家们向他寻求帮助。因诺肯蒂正忙于准备VK杯,因此他决定将问题委托给参赛者。帮助科学家吧!

输入

第一行包含描述初始 DNA 链的字符串 s (1 ≤ |s| ≤ 105)。它仅由大写英文字母“A”、“T”、“G”和“C”组成。

下一行包含单个整数 q (1 ≤ q ≤ 105) — 事件数。

之后是 q 行,每行描述一个事件。每行都具有以下两种格式之一:

- 1 x c,其中x是整数(1 ≤ x ≤ |s|),c是字母“A”、“T”、“G”或“C”,这意味着DNA发生了变化:位置x的核苷酸现在是c。
- 2 l r e,其中l、r是整数(1 ≤ l ≤ r ≤ |s|),e是一串字母“A”、“T”、“G”和“C”(1 ≤ |e| ≤ 10),这意味着科学家对感染e的影响值感兴趣指从位置 l 到位置 r(含)的 DNA 链片段。

输出

对于每个科学家的查询(第二种类型查询),在新行中打印一个整数 - 感染对 DNA 的影响值。

示例

输入 #1

ATGCATGC
4
2 1 8 ATGC
2 2 6 TTT
1 4 T
2 2 6 TA

输出 #1

8
2
4

输入 #2

GAGTTGTTAA
6
2 3 4 TATGGTG
1 1 T
1 6 G
2 5 9 AGTAATA
1 10 G
2 2 6 TTGT

输出 #2

0
3
1

注意

考虑第一个例子。在第二个类型的第一个查询中,所有字符都一致,因此答案是 8。在第二个查询中,我们比较字符串“TTTTT...”和子字符串“TGCAT”。有两场比赛。在第三个查询中,DNA 更改后,我们将字符串“TATAT...”与子字符串“TGTAT”进行比较。有 4 场比赛。