#P4924. [Lydsy1706月赛]原谅字符串
[Lydsy1706月赛]原谅字符串
题目描述
小 Q 给自己戴了一顶“原谅帽”。长度相同的两个字符串,只要对应字符不同的位置不超过 个,他就认为它们匹配。
用 表示字符串 中从第 个到第 个字符组成的子串。 表示 中与模式串 匹配的连续子串个数,按起点计数,子串可以重叠。
小 Q 有一个下标从 开始的十进制数字串 ,要处理以下操作。
+ l r k:对每个 ,将 改为 。? l r P:查询 。
输入格式
第一行包含一个正整数 ,表示测试数据组数,满足 。
每组数据的第一行包含两个正整数 ,分别表示字符串长度和操作数,满足 。第二行是长度为 的十进制数字串 。
接下来 行,每行描述一个操作,满足 。对修改操作,。对查询操作, 是十进制数字串。
每组数据中所有查询的 总和不超过 。整个输入中至多 组数据满足 。
输出格式
每次查询输出一行一个整数,表示匹配的子串数量。
样例
1
5 5
01234
? 2 5 1234
? 2 5 1777
? 2 5 9999
+ 1 5 5
? 1 5 56789
1
1
0
1
相关
在下列比赛中: