【题解】P5287 [HNOI2019] JOJO

· · 题解

由于可以离线，那么我们建出版本树，然后转化为 push_back/pop_back 操作，那么我们需要维护一个可撤销 kmp。

观察到，如果现在我们求出了前 i 段字符的 border，现在插入 k 个 c，则我们要求这个 broder 的前缀部分是需要匹配 k 个 c。由于相邻的段字符一定不一样，故一个 border 的右边界一定落在某个段的右端点。

那么暴力匹配就简单了，一直跳 border，检查是否匹配。注意，我们可能匹配到 c，但是段的长度不一样。只有长度完全等于 k 的时候，才能成为 i+1 的 border。那么同时我们可以处理出段内的 border。

一段暴力的代码：

for(int j=F[i],mx=0;j;j=F[j]) //F is broder
  if(s[j+1]==c)
  {
    LL ly=min(k,max(mx,len[j+1]));
    res+=(ly-mx)*(2*pre[j]+ly+mx+1)/2,mx=ly;
    //pre is the prefix total length
    if(len[j+1]==k&&!F[i+1]) F[i+1]=j+1;
  }

考虑优化。根据一些 border theorem，有：

由于一个等差数列的最小周期都相同，则他们可以匹配的也是相同的。那么我们可以只检测一个等差数列中最长和次长的 border，于是可以在 O(\log n) 复杂度内完成 fail 的转移。

注意，若第一段是字符 c，则需要特殊处理，这里是可以匹配 border 的。

::::info[为什么还需要检测次长？] 这是由于最长的 border 后面接的可能不是一段完整的段（就是周期被从中间截断了），那么此时次长的才有可能成为新的 border。 ::::

那么我们在维护 fail 的同时维护等差数列的末尾是哪项即可。

::::info[code]

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e5+10,P=998244353;
LL n,ans[N],sum,F[N],sk[N];//F is border
LL len[N],s[N],pre[N];
struct zxz { LL c,x; }t[N];
vector<LL> e[N];
bool operator !=(vector<LL> a,vector<LL> b)
{
    if(a.size()!=b.size()) return 1;
    for(int i=0;i<a.size();i++)
        if(a[i]!=b[i]) return 1;
    return 0;
}
LL ins(LL i,LL c,LL cnt)
{
    if(i==0) return F[1]=0,pre[1]=len[1]=cnt,s[1]=c,cnt*(cnt-1)/2;
    LL mx=0,res=0; F[i+1]=0;
    for(int j=F[i];j;j=sk[j])
    {
        if(s[j+1]==c)
        {
            LL ly=min(cnt,max(mx,len[j+1]));
            res+=(ly-mx)*(2*pre[j]+ly+mx+1)/2,mx=ly;
            if(len[j+1]==cnt&&!F[i+1]) F[i+1]=j+1;
        }
        j=F[j];
        if(j&&s[j+1]==c)
        {
            LL ly=min(cnt,max(mx,len[j+1]));
            res+=(ly-mx)*(2*pre[j]+ly+mx+1)/2,mx=ly;
            if(len[j+1]==cnt&&!F[i+1]) F[i+1]=j+1;
        }
    }
    if(s[1]==c)
    {
        LL ly=min(cnt,max(mx,len[1]));
        res+=(ly-mx)*(ly+mx+1)/2,mx=ly;
        if(len[1]<=cnt&&!F[i+1]) F[i+1]=1;
        res+=(cnt-mx)*mx;
    }
    i++;
    len[i]=cnt,pre[i]=pre[i-1]+cnt,s[i]=c;
    sk[i]=(pre[F[i]]-pre[F[F[i]]]==pre[i]-pre[F[i]]?sk[F[i]]:F[i]);
    return res;
}
void dfs(LL u,LL dep=0)
{
    ans[u]=sum;
    for(auto v:e[u])
    {
        if(!t[v].x) { dfs(v,dep); continue; }
        LL zxz=ins(dep,t[v].c,t[v].x)%P;
        sum=(sum+zxz)%P;
        dfs(v,dep+1);
        sum=(sum-zxz+P)%P;
    }
}
int main()
{
    scanf("%lld",&n); LL u=0;
    for(int i=1;i<=n;i++)
    {
        LL op,x; char c[3]; scanf("%lld%lld",&op,&x);
        if(op==1) scanf("%s",c),t[i]={c[0],x},e[u].push_back(i);
        else e[x].push_back(i);
        u=i; 
    }
    dfs(0);
    for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
    return 0;
}

::::