*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 \(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\cdot 10^5\) consisting only of
characters a-z. Please compute \(A(t)\), and how \(A(t)\) would change after \(U\)
(\(1\le U\le 2\cdot 10^5\)) updates, each changing a character of \(t\). Updates
are cumulative.

Problem credits: Brandon Wang and Benjamin Qi

SCORING

• Input 2: \(|t|, U\le 300\)
• Inputs 3-5: \(U\le 10\)
• Inputs 6-13: \(|t|, U\le 10^5\)
• Inputs 14-21: No additional constraints.

Problem credits: Brandon Wang and Benjamin Qi

The first line of input contains \(t\).

The next line contains \(U\), followed by \(U\) lines each containing a position \(p\)
(\(1\le p\le N\)) and a character \(c\) in the range a-z, meaning that the \(p\)th
character of \(t\) is changed to \(c\).

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.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > US Open > Platinum