Simple String Queries

题目描述

给你一个长度为 $N$ 的字符串 $S$，由小写英文字母组成。 处理 $Q$ 个以下两种类型的查询：

类型 $1$：将 $S$ 的第 $i_q$ 个字符更改为 $c_q$。（如果第 $i_q$ 个字符已经是 $c_q$ 则不做任何操作。） 类型 $2$：回答在字符串 $S$ 中第 $l_q$ 到第 $r_q$ 个字符（包含端点）所形成的子串中出现的不同字符的数量。

输入格式

输入按下列格式从标准输入给出： $N$ $S$ $Q$ $Query_1$ $\vdots$ $Query_Q$

其中，第 $4$ 行到第 $(Q+3)$ 行的 $Query_i$ 为下列其中一种格式： $1$ $i_q$ $c_q$

$2$ $l_q$ $r_q$

输出格式

对于每个类型 $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

提示

$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$ 每个测试用例中至少有一个类型 $2$ 的查询。在第一个查询中，$cdbb$ 包含三种字母：$b$、$c$ 和 $d$，所以我们输出 $3$。 在第二个查询中，$S$ 被修改为 $abcdzbd$。 在第三个查询中，$a$ 包含一种字母：$a$，所以我们输出 $1$。 在第四个查询中，$S$ 被修改为 $abcazbd$。 在第五个查询中，$S$ 没有改变，仍然是 $abcazbd$。 在第六个查询中，$abcazbd$ 包含五种字母：$a$、$b$、$c$、$d$ 和 $z$，所以我们输出 $5$。

标签: AtCoder|abc157E

来源

AtCoder|abc157E