#P9192. [USACO23OPEN] Pareidolia P
[USACO23OPEN] Pareidolia P
题目描述
Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string bqessiyexbesszieb
, Farmer John's eyes ignore some of the letters and all he sees is bessiebessie
.
Given a string , let represent the maximum number of repeated copies of bessie
one can form by deleting zero or more of the characters from . In the example above, . Furthermore, given a string , let represent the sum of over all contiguous substrings of .
Farmer John has a string t of length at most consisting only of characters a-z. Please compute A(t), and how A(t) would change after updates, each changing a character of t. Updates are cumulative.
输入格式
The first line of input contains .
The next line contains , followed by lines each containing a position and a character in the range a-z, meaning that the pth character of is changed to .
输出格式
Output lines, the total number of bessies that can be made across all substrings of before any updates and after each update.
题目大意
题目描述
Pareidolia 是一种现象,指的是人们倾向于在并不真正存在的地方看到熟悉的图案——例如在云中看到一张脸。可以想象,由于农夫 John 经常与奶牛接触,他常常在日常物品中看到与奶牛相关的图案。例如,如果他看到字符串 bqessiyexbesszieb
,农夫 John 的眼睛会忽略其中的一些字母,而他看到的只是 bessiebessie
。
给定一个字符串 ,令 表示通过删除 中的零个或多个字符后,能够形成的 bessie
的最大重复次数。在上面的例子中,。此外,给定一个字符串 ,令 表示所有连续子串 的 之和。
农夫 John 有一个长度不超过 的字符串 ,且仅由字符 a-z 组成。请计算 ,以及在 次更新后 的变化情况,每次更新会修改 中的一个字符。更新是累积的。
输入格式
第一行输入包含 。
接下来的一行包含 ,随后是 行,每行包含一个位置 和一个字符 (范围为 a-z),表示将 的第 个字符修改为 。
输出格式
输出 行,分别表示在没有任何更新之前以及每次更新后, 的所有子串中能够形成的 bessie
的总数。
提示
在没有任何更新之前,有 12 个子串恰好包含 个 bessie
,有 个子串恰好包含 个 bessie
,因此 bessie
的总数为 。
第一次更新后, 变为 belsiebessie
。有 7 个子串恰好包含一个 bessie
。
第二次更新后, 变为 belsiesessie
。只有整个字符串包含 bessie
。
输入 :;
输入 :;
输入 :;
输入 :没有额外限制。
bessiebessie
3
3 l
7 s
3 s
14
7
1
7
提示
Before any updates, twelve substrings contain exactly bessie
and string contains exactly bessie
s, so the total number of bessies is .
After one update, is belsiebessie
. Seven substrings contain exactly one bessie
.
After two updates, is belsiesessie
. Only the entire string contains bessie
.
Input : ;
Inputs : ;
Inputs : ;
Inputs : No additional constraints.