E - 简单字符串查询

分数：500分

问题描述

给定一个长度为N的字符串S，由小写英文字母组成。

处理Q个以下两种查询：

• 类型1：将S的第i_q个字符更改为c_q。 （如果第i_q个字符已经是c_q，则不执行任何操作。）
• 类型2：回答S的从第l_q个字符到第r_q个字符（包括）之间的子串中出现的不同字符的数量。

约束

• N，Q，i_q，l_q和r_q都是整数。
• S是由小写英文字母组成的字符串。
• c_q是小写英文字母。
• 1 ≤ N ≤ 500000
• 1 ≤ Q ≤ 20000
• |S| = N
• 1 ≤ i_q ≤ N
• 1 ≤ l_q ≤ r_q ≤ N
• 每个测试用例中至少有一个类型2查询。

输入

输入的格式如下：

N

S

Q

Query_1

...

Query_Q

这里，第4至第(Q+3)行的Query_i是以下之一：

1 i_q c_q

2 l_q r_q

输出

对于每一个类型2的查询，输出一行包含答案。

样例解释

样例输入1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

样例输出1

3
1
5

在第一个查询中，字符串cdbb包含三种字符：b，c和d，所以我们输出3。

在第二个查询中，字符串S被修改为abcdzbd。

在第三个查询中，字母a包含一种字符：a，所以我们输出1。

在第四个查询中，字符串S被修改为abcazbd。

在第五个查询中，字符串S不变，仍为abcazbd。

在第六个查询中，字符串abcazbd包含五种字符：a，b，c，d和z，所以我们输出5。