Pareidolia (USACO Platinum 2023 US Open)

Pareidolia (USACO Platinum 2023 US Open)

首先,对于静态的tt,一个计算A(t)的O(t2)\mathcal{O}(|t|^2)办法,是对于所有tt的后缀,greedy地扫描匹配"bessie",每匹配到一次, 就 ans += k+1,k是此时字符串剩下的字符个数。

这个办法可以优化到O(t)\mathcal{O}(|t|),办法是同时模拟所有后缀的状态机,对于每一个位置ii:

  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]节点维护以下值:

然后就是标准的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;
}