[题解] [USACO23OPEN] Pareidolia P

· · 题解

首先考虑对于单独的一个数列应该怎么做。

记字符串 bessie 为 T，为了方便，T 的下标从 0 开始。

考虑一个 dp：记 f_{i,j} 为考虑前 i 个字符，下一个需要匹配的是 T 的第 j 位的后缀个数。

那么有转移：f_{i-1,j}\to f_{i,(j+[s_i=T_j])\bmod 6}，1\to f_{i,[s_i=T_0]}，f_{i-1,5}[s_i=T_6]\to ans。

考虑用 cdq 分治维护这个过程，记当前分治区间为 [l,r]，已经计算好了 [l,mid],(mid,r] 的对答案的贡献，现在需要计算横跨 mid 的所有子串对答案的贡献。

对于每个区间，记录 nxt_i 表示进入这个区间时下一个需要匹配 T_i，离开这个区间时下一个需要匹配 T_{nxt_i}，cnt_i 表示离开区间时下一个需要匹配 T_i 的后缀个数，co_i 表示进入区间时下一个需要匹配 T_i 的字符串在当前区间中有多少个位置可以对答案产生贡献。

合并 [l,mid],(mid,r] 两个区间时，对答案的贡献即为 \sum cnt_{[l,mid],i}co_{(mid,r],i}，nxt,cnt,co 的合并都是容易的。

这个分治的过程显然可以用线段树维护，时间复杂度 \mathcal O(|T|n\log n)

code:

#include<bits/stdc++.h>
#define int long long
#define MAXN 200010
using namespace std;
const string base="bessie";
int n,Q;
char s[MAXN];
struct tnode{
    int nxt[6],cnt[6],co[6],sum;
    tnode(char c='#',int pos=0){
        memset(nxt,0,sizeof(nxt));memset(cnt,0,sizeof(cnt));
        memset(co,0,sizeof(co));sum=0;
        if(pos){
            for(int i=0;i<6;i++)nxt[i]=(c==base[i]?(i+1)%6:i);
            cnt[nxt[0]]=1;co[5]=(c=='e'?n-pos+1:0);
        }
    }
};
tnode operator+(tnode ql,tnode qr){
    tnode ret;ret.sum=ql.sum+qr.sum;
    for(int i=0;i<6;i++){
        ret.nxt[i]=qr.nxt[ql.nxt[i]];
        ret.cnt[i]+=qr.cnt[i];ret.cnt[qr.nxt[i]]+=ql.cnt[i];
        ret.co[i]=ql.co[i]+qr.co[ql.nxt[i]];
        ret.sum+=ql.cnt[i]*qr.co[i];
    }
    return ret;
}
struct Segtree{
    tnode t[MAXN<<2];
    void pushup(int p){t[p]=t[p<<1]+t[p<<1|1];}
    void build(int p,int l,int r){
        if(l==r)return (void)(t[p]=tnode(s[l],l));int mid=(l+r)>>1;
        build(p<<1,l,mid);build(p<<1|1,mid+1,r);pushup(p);
    }
    void update(int p,int l,int r,int pos,char d){
        if(l==r)return (void)(t[p]=tnode(d,l));
        int mid=(l+r)>>1;
        if(pos<=mid)update(p<<1,l,mid,pos,d);
        else update(p<<1|1,mid+1,r,pos,d);
        pushup(p);
    }
}T;
signed main(){
    scanf("%s%lld",s+1,&Q);n=strlen(s+1);
    T.build(1,1,n);
    printf("%lld\n",T.t[1].sum);
    while(Q--){
        int pos;char opt[2];scanf("%lld%s",&pos,opt);
        T.update(1,1,n,pos,opt[0]);
        printf("%lld\n",T.t[1].sum);
    }
    return 0;
}