字符串查询

题目描述

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

请处理 $Q$ 个查询。每个查询是以下两种之一:

• type $1$:将 $S$ 的第 $i_q$ 个字符改为 $c_q$。如果 $S$ 的第 $i_q$ 个字符本来就是 $c_q$,则不进行任何操作。
• type $2$:回答由 $S$ 的第 $l_q$ 到第 $r_q$ 个字符(含两端)组成的子串中出现了多少种字符。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$
$Q$
$Query_1$
$\vdots$
$Query_Q$

第 $4$ 行到第 $Q+3$ 行的 $Query_i$ 是以下两种之一:

$1$ $i_q$ $c_q$

表示进行 type $1$ 的操作。

$2$ $l_q$ $r_q$

表示进行 type $2$ 的操作。

输出格式

对于每个 type $2$ 的查询,将答案用换行分隔输出。

样例

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

3
1
5

第 $1$ 个查询中,cdbb 包含 b、c、d 共 $3$ 种字符,因此输出 $3$。

第 $2$ 个查询使 $S$ 变为 abcdzbd。

第 $3$ 个查询中,a 包含 a 共 $1$ 种字符,因此输出 $1$。

第 $4$ 个查询使 $S$ 变为 abcazbd。

第 $5$ 个查询中,$S$ 保持不变,仍为 abcazbd。

第 $6$ 个查询中,abcazbd 包含 a, b, c, d, z 共 $5$ 种字符,因此输出 $5$。

数据范围

• $N, Q, i_q, l_q, r_q$ 是整数
• $S$ 是由小写英文字母组成的字符串
• $c_q$ 是小写英文字母
• $1 \leq N \leq 500000$
• $1 \leq Q \leq 20000$
• $|S| = N$
• $1 \leq i_q \leq N$
• $1 \leq l_q \leq r_q \leq N$
• 每个测试用例中至少有一个 type $2$ 的查询