#PU1332. USACO 2023 US Open Contest, Platinum — Problem 1. Pareidolia
USACO 2023 US Open Contest, Platinum — Problem 1. Pareidolia
USACO 2023 US Open Contest, Platinum — Problem 1. Pareidolia
题目描述
Note: The time limit for this problem is 4s, twice the default. The memory limit for this problem is 512MB, twice the default. 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, "bqessiyexbesszieb". Furthermore, given a string , let represent the sum of over all contiguous substrings of . Farmer John has a string of length at most consisting only of characters a-z. Please compute , and how would change after () updates, each changing a character of . 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 th character of is changed to .
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
bessiebessie
3
3 l
7 s
3 s
14
7
1
7
Before any updates, twelve substrings contain exactly 1 "bessie" and 1 string
contains exactly 2 "bessie"s, so the total number of bessies is
$12\cdot 1 + 1 \cdot 2 = 14$.
After one update, $t$ is "belsiebessie." Seven substrings contain exactly one
"bessie."
After two updates, $t$ is "belsiesessie." Only the entire string contains
"bessie."