#P4924. [Lydsy1706月赛]原谅字符串

    ID: 4029 传统题 8000ms 256MiB 尝试: 55 已通过: 6 难度: 8 上传者: 标签>难度分类提高+/省选-位运算位集加速字符串匹配动态规划线性 DP滚动数组数据结构整块懒标记位计数CF2400claris原创本oj版权所有翻版必究

[Lydsy1706月赛]原谅字符串

题目描述

小 Q 给自己戴了一顶“原谅帽”。长度相同的两个字符串,只要对应字符不同的位置不超过 33 个,他就认为它们匹配。

用 S[l,r]S[l,r] 表示字符串 SS 中从第 ll 个到第 rr 个字符组成的子串。occ⁡(P,U)\operatorname{occ}(P,U) 表示 UU 中与模式串 PP 匹配的连续子串个数,按起点计数,子串可以重叠。

小 Q 有一个下标从 11 开始的十进制数字串 SS,要处理以下操作。

  • + l r k:对每个 l≤i≤rl\le i\le r,将 SiS_i 改为 (Si+k) mod 10(S_i+k)\bmod 10。
  • ? l r P:查询 occ⁡(P,S[l,r])\operatorname{occ}(P,S[l,r])。

输入格式

第一行包含一个正整数 TT,表示测试数据组数,满足 1≤T≤151\le T\le 15。

每组数据的第一行包含两个正整数 n,mn,m,分别表示字符串长度和操作数,满足 1≤n,m≤50 0001\le n,m\le 50\,000。第二行是长度为 nn 的十进制数字串 SS。

接下来 mm 行,每行描述一个操作,满足 1≤l≤r≤n1\le l\le r\le n。对修改操作,1≤k≤91\le k\le 9。对查询操作,PP 是十进制数字串。

每组数据中所有查询的 ∣P∣|P| 总和不超过 100 000100\,000。整个输入中至多 44 组数据满足 min⁡(n,m)>1000\min(n,m)>1000。

输出格式

每次查询输出一行一个整数,表示匹配的子串数量。

样例

1
5 5
01234
? 2 5 1234
? 2 5 1777
? 2 5 9999
+ 1 5 5
? 1 5 56789
1
1
0
1