题解：动态维护子串的 bessie 匹配数

问题转化

定义 $B(s)$ 为从字符串 $s$ 中删除若干字符后能得到的形如 bessie 重复串中 bessie 的最大出现次数。

$A(t) = \sum_{t的所有子串\ s} B(s)$。

支持单点修改 $t$ 的字符，每次询问修改后的 $A(t)$。

$|t|, U \le 2\times 10^5$。

关键观察

$B(s)$ 等价于按顺序匹配 bessie 这个单词能匹配多少次。

设模式串 $P = \text{"bessie"}$，长度 $L=6$。

$B(s)$ 就是 $s$ 作为序列，能完整匹配 $P$ 的最大次数，允许跳过字符。

自动机模型

建立自动机：状态 $0$ 表示未开始匹配，状态 $i(1\le i\le 6)$ 表示已匹配到 bessie 的第 $i$ 个字符。状态 $6$ 匹配完一个 bessie 后回到状态 $0$（因为可以连续匹配）。

实际上：匹配完一次 bessie 后，最后一个 e 同时也是下一个 bessie 中 b 的前一个字符，所以状态转移是：

• 在状态 $i$，若下一个字符等于 $P[i+1]$（下标从 1 开始），则转移到状态 $i+1$（若 $i=6$ 则转移到状态 $1$ 并计数 +1）。
• 否则停留在状态 $i$（跳过字符）。

但为了统计 $B(s)$ 的值，我们需要知道在扫描 $s$ 时能完成多少次完整匹配。

动态规划计算 $B(s)$

设 $dp[i]$ 表示扫描到当前位置时，已经匹配了 $i$ 个 bessie 的字符（$0\le i\le 5$，$i=5$ 时再遇到 e 就完成一次）。
但为了计算 $B(s)$，我们需要知道最大匹配次数，这等价于贪心匹配：尽可能早地完成每一次 bessie。

所以 $B(s)$ 就是从左到右贪心匹配 bessie 能得到的次数。

计算所有子串的 $B(s)$ 和

考虑每个子串 $t[l..r]$，它的 $B$ 值就是从左到右扫描该子串能匹配到的 bessie 个数。

固定左端点 $l$，当右端点 $r$ 右移时，$B(t[l..r])$ 可能增加（当完成一次 bessie 匹配时）。

定义 $next[l]$ 为从位置 $l$ 开始贪心匹配一个 bessie 结束的位置的下一个位置（即匹配完一次 bessie 后的下一个位置）。若无法匹配则 $next[l] = \infty$。

则 $B(t[l..r])$ 等于从 $l$ 开始，不断跳 $next$ 直到超过 $r$ 的跳跃次数。

转化为计数问题

$A(t) = \sum_{l\le r} B(t[l..r]) = \sum_{l} \sum_{r\ge l} B(t[l..r])$。

固定 $l$，考虑右端点 $r$ 从 $l$ 到 $n$ 移动，$B(t[l..r])$ 是一个分段常数函数，每当 $r$ 经过一个 $next$ 跳跃点时增加 $1$。

设从 $l$ 开始能匹配到 $k$ 个 bessie，第 $i$ 个 bessie 的结束位置为 $e_i$（即跳 $i$ 次 $next$ 后的位置的前一个位置），则：

• 对于 $r < e_1$，$B=0$
• 对于 $e_1 \le r < e_2$，$B=1$
• ...
• 对于 $e_{k-1} \le r < e_k$，$B=k-1$
• 对于 $r \ge e_k$，$B=k$

所以固定 $l$ 的贡献为：

$$\sum_{i=1}^{k} i \times (e_{i+1} - e_i)$$

其中 $e_{k+1}=n+1$。

计算总贡献

$A(t) = \sum_{l=1}^n \sum_{i=1}^{k_l} i \times (e_{l,i+1} - e_{l,i})$。

交换求和顺序：

$$A(t) = \sum_{i\ge 1} i \times \sum_{l} (e_{l,i+1} - e_{l,i}) $$

其中 $e_{l,i}$ 是从 $l$ 开始第 $i$ 个 bessie 的结束位置。

高效维护

考虑每个 bessie 的出现对答案的贡献。

若一个 bessie 覆盖区间 $[a,b]$（从位置 $a$ 的 b 开始到位置 $b$ 的 e 结束），则它对哪些子串 $t[l..r]$ 的 $B$ 值有贡献？

当 $l \le a$ 且 $r \ge b$ 时，这个 bessie 会被统计在 $B(t[l..r])$ 中。但还要考虑在 $[l,r]$ 内它是第几个 bessie。

更简单的想法：考虑每个 bessie 的出现，它作为第 $j$ 个 bessie 对答案贡献为 $j \times$ 包含它作为第 $j$ 个 bessie 的子串个数。

自动机 + 数据结构

建立 bessie 的自动机，状态 $0..5$ 表示已匹配的字符数。

扫描字符串，维护每个位置 $i$ 的自动机状态 $st[i]$。

对于每个位置 $i$，若 $t[i]$ 使自动机从状态 $5$（已匹配 bessi）转移到状态 $0$（完成一个 bessie），则说明 $i$ 是一个 bessie 的结束位置。

设这个 bessie 的开始位置为 $start$，则从任意 $l \le start$ 且 $r \ge i$ 的子串都会包含这个完整的 bessie。

但 $B(t[l..r])$ 中这个 bessie 是第几个？这取决于在 $[l,start-1]$ 中已完成了多少个 bessie。

最终算法

1. 预处理 bessie 的自动机。
2. 扫描字符串，记录每个 bessie 出现的开始位置 $L$ 和结束位置 $R$。
3. 维护一个数组 $cnt[x]$ 表示当前位置作为左端点时，已经完成了 $x$ 个 bessie 的左端点个数。
4. 从左到右扫描右端点 $r$：
   • 若 $r$ 是一个 bessie 的结束位置，则它对答案的贡献为 $\sum_{x\ge 0} (x+1) \times cnt[x]$（因为它作为第 $x+1$ 个 bessie 被统计）。
   • 然后更新 $cnt$：所有 $l \le L$ 的左端点完成数 $+1$，即 $cnt[x]$ 转移到 $cnt[x+1]$。
5. 用线段树或 Fenwick 树维护 $cnt$ 数组的区间和与区间平移操作。

单点修改时，重新计算受影响区间的 bessie 出现情况，更新数据结构。

复杂度

• 预处理 $O(n)$
• 每次修改影响 $O(L)$ 个 bessie（$L=6$），更新 $O(\log n)$
• 总复杂度 $O((n+U)\log n)$