Pareidolia (USACO Platinum 2023 US Open)
首先,对于静态的,一个计算A(t)的办法,是对于所有的后缀,greedy地扫描匹配"bessie",每匹配到一次,
就 ans += k+1
,k是此时字符串剩下的字符个数。
这个办法可以优化到,办法是同时模拟所有后缀的状态机,对于每一个位置:
tokenAmts[0]++ // 新开始一个后缀, 即“增加一个模拟的token”
for j in 0..5: // 处理所有状态转移
if t[i] == "bessie"[j]:
if j == 5:
ans += len(t) - i + 1 // 累加答案
newTokenAmts[(j+1) % 6] += tokenAmts[j] // 从j-1状态转移到j状态
tokenAmts = newTokenAmts // 更新tokenAmts
然后我们需要将这个算法翻译到segment tree上,以实现动态修改。每个[l,r]
节点维护以下值:
ans
: 要计算的最终答案nxt[j]
: 进入区间时下一个需要匹配"bessie"[j]
,离开这个区间时下一个需要匹配"bessie"[nxt[j]]
tokenAmts[j]
: 离开区间时下一个需要匹配"bessie"[j]
的后缀个数co[j]
: 进入区间时下一个需要匹配"bessie"[j]
的字符串,在当前区间中对答案的contribution
然后就是标准的segment tree实现就可以,节点合并也比较直观。
如果对最初的贪心算法和优化还有疑问,可以参考以下题解:USACO官方, 浴谷,USACO Guide
#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
int n, u;
char t[200005];
struct Item {
ll ans;
ll nxt[6], tokenAmts[6], co[6];
};
const char *base = "bessie";
Item tree[800005];
void merge(int x) {
tree[x].ans = tree[2*x].ans + tree[2*x+1].ans;
memset(tree[x].tokenAmts, 0, sizeof(tree[x].tokenAmts));
for (int j = 0; j < 6; j++) {
tree[x].nxt[j] = tree[2*x+1].nxt[tree[2*x].nxt[j]];
tree[x].tokenAmts[j] += tree[2*x+1].tokenAmts[j];
tree[x].tokenAmts[tree[2*x+1].nxt[j]] += tree[2*x].tokenAmts[j];
tree[x].co[j] = tree[2*x].co[j] + tree[2*x+1].co[tree[2*x].nxt[j]];
tree[x].ans += tree[2*x].tokenAmts[j] * tree[2*x+1].co[j];
}
}
Item new_node(int l) {
Item r;
r.ans = 0;
for (int j = 0; j < 6; j++) {
r.nxt[j] = t[l] == base[j] ? (j + 1) % 6 : j;
r.tokenAmts[j] = 0;
r.co[j] = 0;
}
r.tokenAmts[r.nxt[0]] = 1;
r.co[5] = t[l] == 'e' ? n - l : 0;
return r;
}
void build(int x=1, int l=0, int r=n-1) {
if (l == r) {
tree[x] = new_node(l);
} else {
int mid = (l+r)/2;
build(2*x, l, mid);
build(2*x+1, mid+1, r);
merge(x);
}
}
void modify(int i, char c, int x=1, int l=0, int r=n-1) {
if (l == r) {
t[l] = c;
tree[x] = new_node(l);
} else {
int mid = (l+r)/2;
if (i <= mid) modify(i, c, 2*x, l, mid);
else modify(i, c, 2*x+1, mid+1, r);
merge(x);
}
}
int main()
{
scanf("%s", t);
n = strlen(t);
build();
printf("%lld\n", tree[1].ans);
scanf("%d", &u);
for (int i = 0; i < u; i++) {
int p;
char c;
scanf("%d %c", &p, &c);
modify(p-1, c);
printf("%lld\n", tree[1].ans);
}
return 0;
}