CF1234D Distinct Characters Queries
题目描述
给定一个只由小写拉丁字母构成的字符串 s,以及 q 次关于该字符串的询问。询问分为以下两种类型:
∙修改:给定一个位置 pos 和一个字符 c,将 spos 替换为 c;
∙查询:给定区间 [l,r],求出子串 slsl+1…sr 中不同字符的种类数。
对于每个查询,输出对应的结果。
【名词解释】
∙子串:子串为从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。例如 "codeforces" 的子串有 "code"、"force"、"f"、"for",但没有 "coder"。
输入格式
第一行输入一个字符串 s(1≦∣s∣≦105),仅由小写拉丁字母构成。
第二行输入一个整数 q(1≦q≦105) 代表询问次数。
此后 q 行,第 i 行输入一个整数 ti(ti∈{1,2}) 代表询问类型,随后在同一行上:
∙若 ti=1,输入一个整数 $\mathrm{pos}_i \left(1 \leqq \mathrm{pos}_i \leqq |s|\right)$ 和一个字符 ci,代表把 sposi 修改为 ci,其中 ci 为小写拉丁字母;
∙若 ti=2,输入两个整数 $l_i, r_i \left(1 \leqq l_i \leqq r_i \leqq |s|\right)$,代表一次查询。
保证至少存在一次类型 2 的询问。
输出格式
对于每次类型 2 的询问,新起一行输出一个整数,代表该询问对应子串中不同字符的种类数。输出的行数等于类型 2 询问的次数。
测试样例
abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7
3
1
2
样例 1 解释
初始时,s="abacaba"。
∙第一次询问为 2 1 4,子串为 "abac",包含 ‘a’、‘b’、‘c’ 三种字符,因此答案为 3;
∙第二次询问为 1 4 ‘b’,将 s4 由 ‘c’ 修改为 ‘b’,字符串变为 "abababa";
∙第三次询问为 1 5 ‘b’,将 s5 由 ‘a’ 修改为 ‘b’,字符串变为 "ababbba";
∙第四次询问为 2 4 6,子串为 "bbb",只包含 ‘b’ 一种字符,因此答案为 1;
∙第五次询问为 2 1 7,子串为 "ababbba",包含 ‘a’、‘b’ 两种字符,因此答案为 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
5
2
5
2
6