Statement

给串 \(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;
}