A6915. 不同字符查询
编程题
普及+/提高
知识点
题目描述
给定一个只包含小写拉丁字母的字符串 $s$，以及 $q$ 个关于该字符串的查询。
回忆一下，字符串 $s[l;r]$ 的子串是 $s_l s_{l+1}\dots s_r$。例如，"acgo" 的子串有 "ac”、"go"、"cg"、"acgo"，但没有 "og" 和 "top"。
查询有两种类型：
- $1\ pos\ c$（$1 \le pos \le |s|$，$c$ 为小写拉丁字母）：将 $s_{pos}$ 替换为 $c$（即 $s_{pos}:=c$）。
- $2\ l\ r$（$1 \le l \le r \le |s|$）：计算子串 $s[l;r]$ 中不同字符的数量。
回忆一下，字符串 $s[l;r]$ 的子串是 $s_l s_{l+1}\dots s_r$。例如，"acgo" 的子串有 "ac”、"go"、"cg"、"acgo"，但没有 "og" 和 "top"。
查询有两种类型：
- $1\ pos\ c$（$1 \le pos \le |s|$，$c$ 为小写拉丁字母）：将 $s_{pos}$ 替换为 $c$（即 $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$ 行，每行一个查询，格式如题目描述所示。保证至少有一个第二类查询。
第二行输入一个整数 $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
说明/提示
## 样例解释
把字符串看成下标从 $1$ 开始的数组：
$s=[a,b,a,c,a,b,a]$。
1) 查询 $2\ 1\ 4$：看子串 $s[1;4]=[a,b,a,c]$，不同字符有 $\{a,b,c\}$，所以输出 $3$。
2) 操作 $1\ 4\ b$：把 $s[4]$ 从 $c$ 改成 $b$，现在
$s=[a,b,a,b,a,b,a]$。
3) 操作 $1\ 5\ b$：把 $s[5]$ 从 $a$ 改成 $b$，现在
$s=[a,b,a,b,b,b,a]$。
4) 查询 $2\ 4\ 6$：看子串 $s[4;6]=[b,b,b]$，只有 $\{b\}$，输出 $1$。
5) 查询 $2\ 1\ 7$：看子串 $s[1;7]=[a,b,a,b,b,b,a]$，不同字符有 $\{a,b\}$，输出 $2$。
把字符串看成下标从 $1$ 开始的数组：
$s=[a,b,a,c,a,b,a]$。
1) 查询 $2\ 1\ 4$：看子串 $s[1;4]=[a,b,a,c]$，不同字符有 $\{a,b,c\}$，所以输出 $3$。
2) 操作 $1\ 4\ b$：把 $s[4]$ 从 $c$ 改成 $b$，现在
$s=[a,b,a,b,a,b,a]$。
3) 操作 $1\ 5\ b$：把 $s[5]$ 从 $a$ 改成 $b$，现在
$s=[a,b,a,b,b,b,a]$。
4) 查询 $2\ 4\ 6$：看子串 $s[4;6]=[b,b,b]$，只有 $\{b\}$，输出 $1$。
5) 查询 $2\ 1\ 7$：看子串 $s[1;7]=[a,b,a,b,b,b,a]$，不同字符有 $\{a,b\}$，输出 $2$。