{"problem":{"name":"[USACO23OPEN] Pareidolia P","description":{"content":"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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9192"},"statements":[{"statement_type":"Markdown","content":"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`.\n\nGiven 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$.\n\nFarmer John has a string t of length at most $2\\times10^5$ consisting only of characters a-z. Please compute A(t), and how A(t) would change after $U (1\\le U\\le2\\times10^5)$ updates, each changing a character of t. Updates are cumulative.\n\n## Input\n\nThe first line of input contains $t$.\n\nThe 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 pth character of $t$ is changed to $c$.\n\n## Output\n\nOutput $U+1$ lines, the total number of bessies that can be made across all substrings of $t$ before any updates and after each update.\n\n[samples]\n\n## Note\n\nBefore 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$.\n\nAfter one update, $t$ is `belsiebessie`. Seven substrings contain exactly one `bessie`.\n\nAfter two updates, $t$ is `belsiesessie`. Only the entire string contains `bessie`.\n\nInput $2$: $|t|,U\\le300$;\n\nInputs $3-5$: $U\\le10$;\n\nInputs $6-13$: $|t|,U\\le10^5$;\n\nInputs $14-21$: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9192","tags":["动态规划 DP","线段树","USACO","2023","矩阵加速"],"sample_group":[["bessiebessie\n3\n3 l\n7 s\n3 s","14\n7\n1\n7"]],"created_at":"2026-03-03 11:09:25"}}