给串 \(t\)，定义 \(B(s)\) 为 \(s\) 删一些字符后能出现最多多少个 bessie，\(A(t)\) 表示对 \(t\) 的所有子串 \(s\) 求 \(B(s)\) 的和，有 \(q\) 次单点修改，每次改完输出 \(B(s)\).
Solution
动态 dp，但是带矩乘 \(6^3\) 常数，不好.
还是考虑分治咋做.
现在有区间 \([l,mid],[mid+1,r]\)
对于一个跨过中点的区间 \([x,y]\)，有个贪心策略：
\(x\to mid\) 这段贪心的匹配 bessie（遇到一个匹配一个），
\(y\to mid+1\) 这段从右往左贪心的匹配 bessie（遇到一个匹配一个，\(\texttt e\to\texttt i\to\texttt s\to\cdots\)）
如果左边匹配完还多余的一段，与右边匹配完还多余的一段，可以凑成一个 bessie，答案加一。
例如 \(x\to mid\) 左边这段最后匹配到 bes，\(y\to mid+1\) 右边这段最后匹配到 ssie，那么答案会多一。
于是答案 \(=\) \([x,mid]\) 的答案 \(+\) \([mid+1,y]\) 的答案 \(+\) \([\)是否多贡献 \(1\)\(]\)
如果固定 \(x\)、移动 \(y\)，“\([x,mid]\) 的答案”对总答案的贡献是 “\([x,mid]\) 的答案” \(\times\) \((r-(mid+1)+1)\)
那么不固定 \(x\)、移动 \(y\)，“\([x,mid]\) 的答案”对总答案的贡献是 “所有 \(x\) 对应的 \([x,mid]\) 的答案之和” \(\times\) \(R.len\)
类似的，“\([mid+1,y]\) 的答案”对总答案的贡献是 “所有 \(y\) 对应的 \([mid+1,y]\) 的答案之和” \(\times\) \(L.len\)
那么 \([\)是否多贡献 \(1\)\(]\) 对总答案的贡献是多少呢？
可以通过：
- 左区间：每个后缀贪心的匹配，最后匹配到
bessie每个位置的后缀数 - 右区间：每个前缀贪心的匹配，最后匹配到
bessie每个位置的前缀数
求出
如何求出这两个东西呢？……
通过一堆分析发现，我们需要维护这些东西：
- rval：每个后缀 \(\texttt b\to\texttt e\to\texttt s\to\cdots\) 贪心地匹配，匹配完
bessie的次数之和 - lval：每个前缀 \(\texttt e\to \texttt i\to\texttt s\to\cdots\) 贪心地匹配，匹配完
bessie的次数之和 - len：区间长度
- rcnt[8]：每个后缀 \(\texttt b\to\texttt e\to\texttt s\to\cdots\) 贪心地匹配，最后匹配到
bessie每个位置的后缀数 - lcnt[8]：匹配到
bessie每个位置的前缀数 - rtrans[8]：从左到右，从
bessie第 \(i\) 个位置出发贪心地匹配，最后匹配到bessie哪个位置. - ltrans[8]：从右到左，从第 \(i\) 个位置出发贪心地匹配，匹配到哪个位置.
- rgo[8]：从左到右，从第 \(i\) 个位置出发贪心地匹配，匹配到的轮数.
- lgo[8]：从右到左，匹配的轮数.
得出他们的定义后，合并你是可以手推的。一次合并 \(O(6)\)（我知道这不严谨，但是我就要这么写 ^-^）
在线段树上做就能支持单点改了。。。
Code
push_up 写了巨大麻烦分讨
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
#define mem(a) memset(a, 0, sizeof(a))
#define Mem(a) memset(a, -1, sizeof(a))
typedef long long ll;
const int N = 2e5 + 10;
string s;
int n, m;
struct Item {
ll rcnt[6], lcnt[6], rtrans[6], ltrans[6], rgo[6], lgo[6];
ll len, rval, lval, ans;
Item() {
mem(rcnt), mem(lcnt), mem(rgo), mem(lgo), Mem(rtrans), Mem(ltrans);
len = rval = lval = ans = 0;
}
Item(char c) {
(*this) = Item(), len = 1;
auto Set = [&](int x) {
ltrans[x] = rtrans[x] = x, rgo[x] = lgo[x] = 1;
};
if (c == 'b') rcnt[0] = 1, Set(0);
if (c == 'e') lcnt[5] = 1, Set(1), Set(5);
if (c == 's') Set(2), Set(3);
if (c == 'i') Set(4);
}
Item operator+ (const Item& rhs) const {
Item res;
res.len = len + rhs.len;
res.ans = ans + rhs.ans + rval * rhs.len + rhs.lval * len;
ll sum = 0;
rep(i, 0, 4) {
sum += rhs.lcnt[i + 1];
res.ans += sum * rcnt[i];
}
rep(i, 0, 5) {
if (rtrans[i] == -1) {
res.rtrans[i] = rhs.rtrans[i];
res.rgo[i] = rhs.rgo[i];
} else {
int p = rtrans[i];
if (rhs.rtrans[(p + 1) % 6] == -1) {
res.rtrans[i] = p;
res.rgo[i] = rgo[i];
} else {
res.rtrans[i] = rhs.rtrans[(p + 1) % 6];
res.rgo[i] = rgo[i] + rhs.rgo[(p + 1) % 6];
}
}
if (rhs.ltrans[i] == -1) {
res.ltrans[i] = ltrans[i];
res.lgo[i] = lgo[i];
} else {
int p = rhs.ltrans[i], q = (p + 5) % 6;
if (ltrans[q] == -1) {
res.ltrans[i] = p;
res.lgo[i] = rhs.lgo[i];
} else {
res.ltrans[i] = ltrans[q];
res.lgo[i] = rhs.lgo[i] + lgo[q];
}
}
res.rcnt[i] += rhs.rcnt[i];
res.lcnt[i] += lcnt[i];
}
res.rval = rhs.rval + rval, res.lval = lval + rhs.lval;
ll r1 = 0, l2 = 0;
rep(i, 0, 5) {
int p = rhs.rtrans[(i + 1) % 6];
if (p != -1) res.rcnt[p] += rcnt[i];
else res.rcnt[i] += rcnt[i];
r1 += rcnt[i];
if (i <= 4) {
int cnt = (i + 1 + rhs.rgo[(i + 1) % 6]) / 6;
res.rval += rcnt[i] * cnt;
} else {
int cnt = rhs.rgo[(i + 1) % 6] / 6;
res.rval += rcnt[i] * cnt;
}
p = ltrans[(i + 5) % 6];
if (p != -1) res.lcnt[p] += rhs.lcnt[i];
else res.lcnt[i] += rhs.lcnt[i];
l2 += rhs.lcnt[i];
if (i >= 1) {
int cnt = (6 - i + lgo[(i + 5) % 6]) / 6;
res.lval += rhs.lcnt[i] * cnt;
} else {
int cnt = lgo[(i + 5) % 6] / 6;
res.lval += rhs.lcnt[i] * cnt;
}
}
if (rhs.rgo[0]) res.rcnt[(rhs.rgo[0] - 1) % 6] += len - r1, res.rval += (len - r1) * (rhs.rgo[0] / 6);
if (lgo[5]) res.lcnt[(6 - lgo[5] % 6) % 6] += rhs.len - l2, res.lval += (rhs.len - l2) * (lgo[5] / 6);
return res;
}
} f[N << 2];
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
void up(int u) {
f[u] = f[lc] + f[rc];
}
void build(int u, int l, int r) {
if (l == r) return (void)(f[u] = Item(s[l - 1]));
build(lc, l, mid), build(rc, mid + 1, r), up(u);
}
void upd(int u, int l, int r, int x, char c) {
if (x < l || r < x) return;
if (l == r) return (void)(f[u] = Item(c));
upd(lc, l, mid, x, c), upd(rc, mid + 1, r, x, c), up(u);
}
#undef lc
#undef rc
#undef mid
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> s >> m, n = s.length(), build(1, 1, n), cout << f[1].ans << '\n';
while (m--) {
int p;
char ch;
cin >> p >> ch;
upd(1, 1, n, p, ch);
cout << f[1].ans << '\n';
}
return 0;
}