A4685 | $统计满足条件的子串个数$

来源官方 / 2024

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $N$ 的字符串 $S$。 你需要执行 $Q$ 个操作，第 $i$ 个操作的类型为 $T_i$： - $T_i = 1$：给定一个整数 $X_i$ 和 字符 $C_i$，将字符串 $S$ 中的第 $X_i$ 个字符修改为 $C_i$。 - $T_i = 2$：给定两个字符 $A_i$ 和 $B_i$，统计字符串 $S$ 中有多少「子串」以 $A_i$ 开头，以 $B_i$ 结尾。 「子串」是由字符串中的连续字符组成的一个序列；例如：ab、a、bab 和 ababc 都是字符串 ababc 的子串，而 ac 和 z 不是。 $\large{数据范围}$ - $1 \le N,\ Q \le 10^5$ - $T_i = 1$ 或 $2$ - $1 \le X_i \le N$ - $S$ 中的字符以及 $A_i$，$B_i$，$C_i$ 均为小写字母。 - 所有查询中至少有 $1$ 个为 $T_i = 2$ 类型。 - 题目保证至少 $40\%$ 的数据 $N, Q \le 500$ - 题目保证至少 $10\%$ 的数据操作只有 $T_i = 2$

对于每个测试文件输入格式如下： $\tt{N\ Q}$ $\tt{S}$ $\tt{Query_1}$ $\tt{Query_2}$ $\tt{\vdots}$ $\tt{Query_Q}$ 对于每个 $\tt{Query_i}$ 若 $\tt{T_i = 1}$： $\tt{T_i\ X_i\ C_i}$ 否则： $\tt{T_i\ A_i\ B_i}$

对于所有的 $\tt{T_i = 2}$ 在单独的一行中输出统计的答案。

输入 #1

6 4
abacac
2 a c
1 4 b
2 a b
2 a c

输出 #1

5
3
3

输入 #2

10 17
wfimwkiihw
1 7 z
2 m z
2 f i
1 6 x
1 6 c
2 c w
1 6 w
2 w w
2 f w
1 10 l
1 10 c
2 i j
1 5 s
2 s c
1 4 a
1 10 o
2 w o

输出 #2

输入 #3

8 12
aaaabbbb
2 a a
2 a b
1 2 b
2 a b
1 4 b
1 5 a
2 b a
2 a b
1 7 a
2 a b
2 b a
2 b b

输出 #3

C++ 编辑器

输入

输出