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

AT_abc372_c.[ABC372C] Count ABC Again

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 NN 的字符串 SS。接着给出 QQ 个查询，依次处理。

对于第 ii 个查询：

  • 给定一个整数 XiX_i 和一个字符 CiC_i，将 SS 的第 XiX_i 个字符替换为 CiC_i。然后，输出字符串 SS 中包含 ABC 作为子串的次数。

这里，SS 的 子串 指的是，从 SS 的开头删除 00 个或多个字符，从 SS 的结尾删除 00 个或多个字符后得到的字符串。

例如，ab 是 abc 的子串，但 ac 不是 abc 的子串。

输入格式

输入按以下形式从标准输入给出：

$ N $ $ Q $ $ S $ $ X_1 $ $ C_1 $ $ X_2 $ $ C_2 $ $ \vdots $ $ X_Q $ $ C_Q $

输出格式

输出 QQ 行。第 ii 行 (1≤i≤Q)(1 \le i \le Q) 包含第 ii 个查询的答案。

输入输出样例

  • 输入#1

    7 4
ABCDABC
4 B
3 A
5 C
4 G

    输出#1

    2
1
1
0

  • 输入#2

    3 3
ABC
1 A
2 B
3 C

    输出#2

    1
1
1

  • 输入#3

    15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

    输出#3

    0
0
0
0
1
1
2
2
1
1

说明/提示

约束

  • 3≤N≤2×1053 \le N \le 2×10^5
  • 1≤Q≤2×1051 \le Q \le 2×10^5
  • SS 是由大写字母组成的长度为 NN 的字符串
  • 1≤Xi≤N1 \le Xi \le N
  • CiC_i 是大写字母

示例解释 1

处理每个查询后的 SS 如下：

  • 处理第 11 个查询后：SS 变为 ABCBABC。其中 ABC 作为子串出现了 22 次。
  • 处理第 22 个查询后：SS 变为 ABABABC。其中 ABC 作为子串出现了 11 次。
  • 处理第 33 个查询后：SS 变为 ABABCBC。其中 ABC 作为子串出现了 11 次。
  • 处理第 44 个查询后：SS 变为 ABAGCBC。其中 ABC 作为子串出现了 00 次。

示例解释 2

有时处理查询前后 SS 可能不会发生变化。

输入解题思路，AI测评打分。不知道怎么写?

首页