Pareidolia

题目描述

注意：本题时间限制为 4s，是默认的两倍。内存限制为 512MB，是默认的两倍。

空想性错视（Pareidolia）是一种现象：你的眼睛倾向于在实际上并不存在熟悉图案的图像中看出熟悉的模式——例如在云朵中看见一张脸。可以想象，由于 Farmer John 总是与奶牛为伴，他常常在日常物体中看到与奶牛相关的图案。例如，当他看到字符串 "bqessiyexbesszieb" 时，Farmer John 的眼睛会忽略其中一些字母，而他看到的只有 "bessiebessie"。

给定一个字符串 $s$，令 $B(s)$ 表示通过从 $s$ 中删除零个或多个字符所能得到的重复出现的 "bessie" 的最大份数。在上面的例子中，$B($"bqessiyexbesszieb"$) = 2$。此外，给定一个字符串 $t$，令 $A(t)$ 表示对 $t$ 的所有连续子串 $s$ 的 $B(s)$ 求和。

Farmer John 有一个长度至多为 $2\cdot 10^5$ 的字符串 $t$，只包含 a-z 的字符。请计算 $A(t)$，以及在进行 $U$ 次（$1\le U\le 2\cdot 10^5$）更新（每次将 $t$ 的某个字符改为另一个字符）之后 $A(t)$ 将如何变化。更新是累积的。

输入格式

第一行输入 $t$。 下一行包含 $U$，随后有 $U$ 行，每行包含一个位置 $p$（$1\le p\le N$）和一个 a-z 范围内的字符 $c$，表示将 $t$ 的第 $p$ 个字符修改为 $c$。

输出格式

输出 $U+1$ 行：在没有任何更新之前，以及每次更新之后，$t$ 的所有子串中总共能够组成的 bessie 的数量。

bessiebessie
3
3 l
7 s
3 s

14
7
1
7

提示

在进行任何更新之前，有 12 个子串恰好包含 1 个 "bessie"，并且有 1 个字符串恰好包含 2 个 "bessie"，因此 bessie 的总数为 $12\cdot 1 + 1 \cdot 2 = 14$。 进行一次更新后，$t$ 变为 "belsiebessie." 有 7 个子串恰好包含 1 个 "bessie"。 进行两次更新后，$t$ 变为 "belsiesessie." 只有整个字符串包含 "bessie"。

SCORING: Input 2: $|t|, U\le 300$ Inputs 3-5: $U\le 10$ Inputs 6-13: $|t|, U\le 10^5$ Inputs 14-21: 无额外限制。 题目致谢：Brandon Wang 和 Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum