#CF1234D. 字符种类数询问

字符种类数询问

CF1234D Distinct Characters Queries

题目描述

\hspace{15pt}给定一个只由小写拉丁字母构成的字符串 ss,以及 qq 次关于该字符串的询问。询问分为以下两种类型:

∙ \hspace{23pt}\bullet\,修改:给定一个位置 pos\mathrm{pos} 和一个字符 cc,将 sposs_{\mathrm{pos}} 替换为 cc;

∙ \hspace{23pt}\bullet\,查询:给定区间 [l,r][l, r],求出子串 slsl+1…srs_l s_{l+1} \dots s_r 中不同字符的种类数。

\hspace{15pt}对于每个查询,输出对应的结果。

\hspace{15pt}【名词解释】

∙ \hspace{23pt}\bullet\,子串:子串为从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。例如 "codeforces"\texttt{"codeforces"} 的子串有 "code"\texttt{"code"}、"force"\texttt{"force"}、"f"\texttt{"f"}、"for"\texttt{"for"},但没有 "coder"\texttt{"coder"}。

输入格式

\hspace{15pt}第一行输入一个字符串 s(1≦∣s∣≦105)s \left(1 \leqq |s| \leqq 10^5\right),仅由小写拉丁字母构成。

\hspace{15pt}第二行输入一个整数 q(1≦q≦105)q \left(1 \leqq q \leqq 10^5\right) 代表询问次数。

\hspace{15pt}此后 qq 行,第 ii 行输入一个整数 ti(ti∈{1,2})t_i \left(t_i \in \{1, 2\}\right) 代表询问类型,随后在同一行上:

∙ \hspace{23pt}\bullet\,若 ti=1t_i = 1,输入一个整数 $\mathrm{pos}_i \left(1 \leqq \mathrm{pos}_i \leqq |s|\right)$ 和一个字符 cic_i,代表把 sposis_{\mathrm{pos}_i} 修改为 cic_i,其中 cic_i 为小写拉丁字母;

∙ \hspace{23pt}\bullet\,若 ti=2t_i = 2,输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq |s|\right)$,代表一次查询。

\hspace{15pt}保证至少存在一次类型 22 的询问。

输出格式

\hspace{15pt}对于每次类型 22 的询问,新起一行输出一个整数,代表该询问对应子串中不同字符的种类数。输出的行数等于类型 22 询问的次数。

测试样例

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

样例 1 解释

\hspace{15pt}初始时,s="abacaba"s = \texttt{"abacaba"}。

∙ \hspace{23pt}\bullet\,第一次询问为 2 1 42\ 1\ 4,子串为 "abac"\texttt{"abac"},包含 ‘a’\texttt{`a'}、‘b’\texttt{`b'}、‘c’\texttt{`c'} 三种字符,因此答案为 33;

∙ \hspace{23pt}\bullet\,第二次询问为 1 4 ‘b’1\ 4\ \texttt{`b'},将 s4s_4 由 ‘c’\texttt{`c'} 修改为 ‘b’\texttt{`b'},字符串变为 "abababa"\texttt{"abababa"};

∙ \hspace{23pt}\bullet\,第三次询问为 1 5 ‘b’1\ 5\ \texttt{`b'},将 s5s_5 由 ‘a’\texttt{`a'} 修改为 ‘b’\texttt{`b'},字符串变为 "ababbba"\texttt{"ababbba"};

∙ \hspace{23pt}\bullet\,第四次询问为 2 4 62\ 4\ 6,子串为 "bbb"\texttt{"bbb"},只包含 ‘b’\texttt{`b'} 一种字符,因此答案为 11;

∙ \hspace{23pt}\bullet\,第五次询问为 2 1 72\ 1\ 7,子串为 "ababbba"\texttt{"ababbba"},包含 ‘a’\texttt{`a'}、‘b’\texttt{`b'} 两种字符,因此答案为 22。

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
5
2
5
2
6