#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 ss, let B(s)B(s) represent the maximum number of repeated copies of "bessie" one can form by deleting zero or more of the characters from ss. In the example above, B(B("bqessiyexbesszieb")=2) = 2. Furthermore, given a string tt, let A(t)A(t) represent the sum of B(s)B(s) over all contiguous substrings ss of tt. Farmer John has a string tt of length at most 2⋅1052\cdot 10^5 consisting only of characters a-z. Please compute A(t)A(t), and how A(t)A(t) would change after UU (1≤U≤2⋅1051\le U\le 2\cdot 10^5) updates, each changing a character of tt. Updates are cumulative.

输入格式

The first line of input contains tt. The next line contains UU, followed by UU lines each containing a position pp (1≤p≤N1\le p\le N) and a character cc in the range a-z, meaning that the ppth character of tt is changed to cc.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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."