2761. [Codeforces 828E] DNA进化

【题目描述】

 所有人都知道DNA链是由核苷酸组成的。有四种核苷酸："A", "T", "G", "C"。一个DNA链是核苷酸的序列。科学家决定追踪一个稀有物种的进化，起初它们的DNA链是字符串ｓ。

 这个物种的进化被描述为DNA的一个变化序列。每一个变化都是一些核苷酸的改变，例如在DNA链“AAGC”中可以发生下列变化：第二个核苷酸可以变为“T”所以最终的DNA链是“ATGC”。

科学家知道DNA链的一些片段能被某些未知的感染源影响。他们能用一个核苷酸序列来代表感染源。科学家对是否有一些变化是由这些感染源引起的很感兴趣。因此他们有时想知道一些感染源对一些DNA片段的影响的值。这种值按如下计算：

  把感染源表示为一个字符串ｅ，并让科学家对DNA链中从ｌ到ｒ的片段感兴趣，包括端点。

  字符串eee... 的前缀（也就是由无限多个重复的字符串ｅ组成的字符串）被写在字符串ｓ从ｌ到ｒ下面，包括端点。

  这种影响的值是字符串ｓ中与写在它下面的字母相同的字母的个数。

 作为一个开发者，Innokenty对生物学也很感兴趣，所以科学家找他帮忙。 Innokenty在忙于为“ＶＫ杯”做准备，所以他决定把这个问题委托给参赛者。快来帮助科学家吧！

【输入格式】

第一行是字符串ｓ。它只包含大写英文字母"A", "T", "G" 和"C"。

下一行是一个整数ｑ（１＜＝ｑ＜＝１０＾５），代表研究事件的个数。

接下来是ｑ行，每行描述一个研究事件，包含以下其中一个形式：

１ ｘ　ｃ；ｘ是一个整数，ｃ是"A", "T", "G" 或"C"；意思是DNA中有一个变化：位置ｘ的核苷酸现在是ｃ。

２　ｌ　ｒ　ｅ；ｌ，ｒ是整数，ｅ值由"A", "T", "G" 和"C"组成的一个字符串，；意思是科学家对感染源ｅ对于从ｌ到ｒ的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

【来源】

CodeForces

http://codeforces.com/contest/828/problem/E