题目详情题解（0）讨论（0）提交记录（0）

A35297.统计满足条件的子串个数

普及+/提高

官方

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

给定一个长度为 NN 的字符串 SS。

你需要执行 QQ 个操作，第 ii 个操作的类型为 TiT_i：

  • Ti=1T_i = 1：给定一个整数 XiX_i 和 字符 CiC_i，将字符串 SS 中的第 XiX_i 个字符修改为 CiC_i。
  • Ti=2T_i = 2：给定两个字符 AiA_i 和 BiB_i，统计字符串 SS 中有多少「子串」以 AiA_i 开头，以 BiB_i 结尾。

「子串」是由字符串中的连续字符组成的一个序列；例如：ab、a、bab 和 ababc 都是字符串 ababc 的子串，而 ac 和 z 不是。

数据范围\large{数据范围}

  • 1≤N, Q≤1051 \le N,\ Q \le 10^5
  • Ti=1T_i = 1 或 22
  • 1≤Xi≤N1 \le X_i \le N
  • SS 中的字符以及 AiA_i，BiB_i，CiC_i 均为小写字母。
  • 所有查询中至少有 11 个为 Ti=2T_i = 2 类型。
  • 题目保证至少 40%40\% 的数据 N,Q≤500N, Q \le 500
  • 题目保证至少 10%10\% 的数据操作只有 Ti=2T_i = 2

输入格式

对于每个测试文件输入格式如下：

N Q\tt{N\ Q}
S\tt{S}
Query1\tt{Query_1}
Query2\tt{Query_2}
⋮\tt{\vdots}
QueryQ\tt{Query_Q}

对于每个 Queryi\tt{Query_i} 若 Ti=1\tt{T_i = 1}：

Ti Xi Ci\tt{T_i\ X_i\ C_i}

否则：

Ti Ai Bi\tt{T_i\ A_i\ B_i}

输出格式

对于所有的 Ti=2\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

    1
2
1
10
3
0
1
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

    10
16
13
3
12
10
6
10

说明/提示

样例 1：\bf{样例\ 1：}

  1. 以 a 开头，以 c 结尾的子串共有 55 个：ac，ac，abac，acac，abacac。
  2. 将 S4S_4 修改为 b，SS 变为 ababac。
  3. 以 a 开头，以 b 结尾的子串共有 33 个：ab，ab，abab。
  4. 以 a 开头，以 c 结尾的子串共有 33 个：ac，abac，abacac。
首页