分数: 500 点
问题陈述
给你一个字符串 S 长度 N 由小写英文字母组成。
流程 Q 以下两种类型的查询:
- 类型 1:更改 i_q- 第一个字符 S to c_q。 (如果 i_q- 第一个字符已经 c_q.)
- 类型 2:回答子串中出现的不同字符的个数 S 之间 l_q-th 和 r_q个字符(含)。
约束
- 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 。
输入
输入由标准输入按以下格式给出:
N S Q Query_1 \vdots Query_Q
在这里, Query_i 在 4-th 至 (Q+3)-第行是以下之一:
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.