问题 P: 字符串查询
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：108
解决：36
题目描述
已知一个由$N$个小写字母组成的字符串$S$。
现在对于$S$有$Q$次处理，分为两种类型：
$1$$)$给定$i_q$,$c_q$,将$S$的第$i_q$个字母修改为字母$c_q$。$($如果两者已经相等则不做处理。$)$
$2$$)$给定$l_q$,$r_q$,输出$S$的下标$i$∈$[$$l_q$,$r_q$$]$的字符的出现种数。
数据范围：$N$,$Q$,$i_q$,$l_q$,$r_q$均为整数。
$S$是仅包含小写字母的字符串。
$c_q$是一个小写字母。
$1≤N≤500000$
$1≤Q≤20000$
$|S|=N$
$(1 \leq i_q \leq N)$
$(1 \leq l_q \leq r_q \leq N)$
至少包含一次第二类型的处理。
现在对于$S$有$Q$次处理，分为两种类型：
$1$$)$给定$i_q$,$c_q$,将$S$的第$i_q$个字母修改为字母$c_q$。$($如果两者已经相等则不做处理。$)$
$2$$)$给定$l_q$,$r_q$,输出$S$的下标$i$∈$[$$l_q$,$r_q$$]$的字符的出现种数。
数据范围：$N$,$Q$,$i_q$,$l_q$,$r_q$均为整数。
$S$是仅包含小写字母的字符串。
$c_q$是一个小写字母。
$1≤N≤500000$
$1≤Q≤20000$
$|S|=N$
$(1 \leq i_q \leq N)$
$(1 \leq l_q \leq r_q \leq N)$
至少包含一次第二类型的处理。
输入
输入包含$Q+3$行。
前三行分别为$N，S，Q$。
接下来$Q$行每一行包含一次处理$Query_i$。
$Query_i$有两种形式：
1)1 $i_q$ $c_q$
2)2 $l_q$ $r_q$
前三行分别为$N，S，Q$。
接下来$Q$行每一行包含一次处理$Query_i$。
$Query_i$有两种形式：
1)1 $i_q$ $c_q$
2)2 $l_q$ $r_q$
输出
对于每一次第二类型的$Query_i$,输出一行，包含一个整数。
样例输入 复制
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7样例输出 复制
3
1
5