#P9192. [USACO23OPEN] Pareidolia P

    ID: 10300 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>动态规划 DP线段树USACO2023矩阵加速

[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 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(bqessiyexbesszieb)=2B(bqessiyexbesszieb)=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 t of length at most 2×1052\times10^5 consisting only of characters a-z. Please compute A(t), and how A(t) would change after U(1U2×105)U (1\le U\le2\times10^5) updates, each changing a character of t. Updates are cumulative.

输入格式

The first line of input contains tt.

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

输出格式

Output U+1U+1 lines, the total number of bessies that can be made across all substrings of tt before any updates and after each update.

题目大意

题目描述

Pareidolia 是一种现象,指的是人们倾向于在并不真正存在的地方看到熟悉的图案——例如在云中看到一张脸。可以想象,由于农夫 John 经常与奶牛接触,他常常在日常物品中看到与奶牛相关的图案。例如,如果他看到字符串 bqessiyexbesszieb,农夫 John 的眼睛会忽略其中的一些字母,而他看到的只是 bessiebessie

给定一个字符串 ss,令 B(s)B(s) 表示通过删除 ss 中的零个或多个字符后,能够形成的 bessie 的最大重复次数。在上面的例子中,B(bqessiyexbesszieb)=2B(bqessiyexbesszieb)=2。此外,给定一个字符串 tt,令 A(t)A(t) 表示所有连续子串 ssB(s)B(s) 之和。

农夫 John 有一个长度不超过 2×1052 \times 10^5 的字符串 tt,且仅由字符 a-z 组成。请计算 A(t)A(t),以及在 U(1U2×105)U (1 \le U \le 2 \times 10^5) 次更新后 A(t)A(t) 的变化情况,每次更新会修改 tt 中的一个字符。更新是累积的。

输入格式

第一行输入包含 tt

接下来的一行包含 UU,随后是 UU 行,每行包含一个位置 pp (1pN)(1 \le p \le N) 和一个字符 cc(范围为 a-z),表示将 tt 的第 pp 个字符修改为 cc

输出格式

输出 U+1U+1 行,分别表示在没有任何更新之前以及每次更新后,tt 的所有子串中能够形成的 bessie 的总数。

提示

在没有任何更新之前,有 12 个子串恰好包含 11bessie,有 11 个子串恰好包含 22bessie,因此 bessie 的总数为 121+12=1412 \cdot 1 + 1 \cdot 2 = 14

第一次更新后,tt 变为 belsiebessie。有 7 个子串恰好包含一个 bessie

第二次更新后,tt 变为 belsiesessie。只有整个字符串包含 bessie

输入 22t,U300|t|, U \le 300

输入 353-5U10U \le 10

输入 6136-13t,U105|t|, U \le 10^5

输入 142114-21:没有额外限制。

bessiebessie
3
3 l
7 s
3 s
14
7
1
7

提示

Before any updates, twelve substrings contain exactly 11 bessie and 11 string contains exactly 22 bessies, so the total number of bessies is 121+12=1412⋅1+1⋅2=14.

After one update, tt is belsiebessie. Seven substrings contain exactly one bessie.

After two updates, tt is belsiesessie. Only the entire string contains bessie.

Input 22: t,U300|t|,U\le300;

Inputs 353-5: U10U\le10;

Inputs 6136-13: t,U105|t|,U\le10^5;

Inputs 142114-21: No additional constraints.