8199: USACO 2023 US Open Contest, Platinum Problem 1. Pareidolia
[Creator : ]
Description
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 s, let B(s) represent the maximum number of repeated copies of "bessie" one can form by deleting zero or more of the characters from s. In the example above, B("bqessiyexbesszieb")=2. Furthermore, given a string t, let A(t) represent the sum of B(s) over all contiguous substrings s of t.
Farmer John has a string t of length at most $2⋅10^5$ consisting only of characters a-z. Please compute A(t), and how A(t) would change after $U\ (1≤U≤2⋅10^5)$ updates, each changing a character of t. Updates are cumulative.
Given a string s, let B(s) represent the maximum number of repeated copies of "bessie" one can form by deleting zero or more of the characters from s. In the example above, B("bqessiyexbesszieb")=2. Furthermore, given a string t, let A(t) represent the sum of B(s) over all contiguous substrings s of t.
Farmer John has a string t of length at most $2⋅10^5$ consisting only of characters a-z. Please compute A(t), and how A(t) would change after $U\ (1≤U≤2⋅10^5)$ updates, each changing a character of t. Updates are cumulative.
Input
The first line of input contains t.
The next line contains U, followed by U lines each containing a position p (1≤p≤N) and a character c in the range a-z, meaning that the p-th character of t is changed to c.
The next line contains U, followed by U lines each containing a position p (1≤p≤N) and a character c in the range a-z, meaning that the p-th character of t is changed to c.
Output
Output U+1 lines, the total number of bessies that can be made across all substrings of t before any updates and after each update.
Sample 1 Input
bessiebessie
3
3 l
7 s
3 s
Sample 1 Output
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⋅1+1⋅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."
After one update, t is "belsiebessie." Seven substrings contain exactly one "bessie."
After two updates, t is "belsiesessie." Only the entire string contains "bessie."