← 返回题目列表

Codeforces · 1234/D

D. 不同字符查询

中文机器翻译题面 查看原题

给定一个由小写拉丁字母组成的字符串 $$$s$$$,并对该字符串进行 $$$q$$$ 查询。

回想一下子字符串 $$$s[l;字符串 $$$s$$$ 的 r]$$$ 是字符串 $$$s_l s_{l + 1} \dots s_r$$$。例如,“codeforces”的子字符串是“code”、“force”、“f”、“for”,但不是“coder”和“top”。

有两种类型的查询:

- $$$1~ pos~ c$$$ ($$$1 \le pos \le |s|$$$, $$$c$$$ 为小写拉丁字母): 将 $$$s_{pos}$$$ 替换为 $$$c$$$ (set $$$s_{pos} := c$$$);
- $$$2~ l~ r$$$ ($$$1 \le l \le r \le |s|$$$):计算子串$$$s[l中不同字符的个数; r]$$$。

输入

输入的第一行包含一个字符串 $$$s$$$,由不超过 $$$10^5$$$ 小写拉丁字母组成。

输入的第二行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含查询,每行一个。每个查询都以问题陈述中描述的格式给出。保证至少有一个第二类型的查询。

输出

对于第二种类型的每个查询,打印它的答案 - 该查询中所需子字符串中不同字符的数量。

示例

输入 #1

abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7

输出 #1

3
1
2

输入 #2

dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11

输出 #2

5
2
5
2
6