题解 P5287 【[HNOI2019]JOJO】

· · 题解

（此题考查了对KMP的理解以及乱搞能力有理有据的优化）

首先对于可持久化的操作，我们可以将其离线下来并在操作树上dfs。

题意显然可以转化为对一个字符串做KMP，并求\sum nxt_i。

现在我们考虑已经有了一些字段，现在要在后面加入一个新的字段，如何计算新字段的贡献。

我们可以从之前的最后一个字符开始跳nxt，如果跳到一个位置，它后面正好有一长串长度为y的c，我们就可以进行匹配。

由于保证了c不同于之前的最后一个字符，我们知道如果nxt跳到某个字段的中间，那么它是一定没有用的，可以自己yy一下。

所以我们定义nxt'_i为从当前的第i个字段的最后一个点开始，一直跳KMP的nxt所跳到的第一个点所在的字段，满足该点是其所在字段的最后一个字符。

以上算法大概是50分，由于数据过水，实际可以AC。

对于hack数据，我们考虑如何使其复杂度正确。（以下优化借鉴于@142857cs的代码orz）

每次跳nxt'时，我们考虑进行一些优化：

如果当前字符串存在周期，我们直接跳到所有周期的第一个。

否则就和原来一样跳nxt。

这样显然每次长度至少/2，复杂度就不需要均摊了，直接就是O(nlogn)

（如有错误请不吝赐教）

代码：


// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>

using std::min;
std::map<std::pair<char,short>,int>ma[100001];
char get(){
    char ch=getchar();
    while(ch<'a'||ch>'z')ch=getchar();
    return ch;
}
int end[100010],pre[100010],cnt,n,length[100010],nxt[100010],ope[100010][2],len,P=998244353,f[100001];
int head[100010],Nxt[200010],b[200010],k,cn;
void push(int s,int t){
    Nxt[++k]=head[s];
    head[s]=k;
    b[k]=t;
}
long long ans[100010],fin[100010],val[100010][3];
inline long long getsum(register long long l,register long long r){
    if(l>r)return 0;
    return (l+r)*(r-l+1)/2;
}
void dfs(int x,int f){
    if(ope[x][0]){
        int tem=nxt[len];
        ++len;
        ans[len]=0;
        val[len][0]=ope[x][0];
        val[len][1]=ope[x][1];
        val[len][2]=val[len-1][2]+ope[x][1];
        nxt[len]=0;
        if(len==1){
            ans[len]=getsum(1,val[1][1]-1);
        }
        else{
            int lastgap=len-tem;
            while(tem&&(val[tem+1][0]!=ope[x][0]||val[tem+1][1]!=ope[x][1])){
                if(tem-nxt[tem]==lastgap)tem=tem%lastgap+lastgap;
                lastgap=tem-nxt[tem];
                tem=nxt[tem];
            }
            if(tem||(val[1][0]==ope[x][0]&&val[1][1]<=ope[x][1]))nxt[len]=tem+1;
            else nxt[len]=tem;
            tem=nxt[len-1];
            lastgap=len-1-tem;
            long long lastlength=0;
            while(lastlength<val[len][1]&&tem){
                if(val[tem+1][0]==ope[x][0]&&val[tem+1][1]>lastlength){
                    ans[len]+=getsum(val[tem][2]+lastlength+1,val[tem][2]+min(val[tem+1][1],val[len][1]));
                    lastlength=val[tem+1][1];
                }
                if(tem-nxt[tem]==lastgap)tem=tem%lastgap+lastgap;
                lastgap=tem-nxt[tem];
                tem=nxt[tem];
            }
            if(lastlength<val[len][1]&&val[1][0]==val[len][0]){
                ans[len]+=getsum(lastlength+1,min(val[len][1],val[1][1]));
                lastlength=std::max(lastlength,min(val[len][1],val[1][1]));
                ans[len]+=val[1][1]*(val[len][1]-lastlength);
            }
            ans[len]+=ans[len-1];
        }
    }
    fin[x]=ans[len];
    for(int i=head[x];i;i=Nxt[i]){
        dfs(b[i],x);
    }
    if(ope[x][0])--len;
}
int read(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
void write(long long x){
    if(x>9)write(x/10);
    putchar((x%10)+'0');
}
signed main(){
    scanf("%d",&n);
    for(int i=1,opt,x;i<=n;i++){
        opt=read(),x=read();
        if(opt==1){
            ope[i][0]=get();
            ope[i][1]=x;
            auto y=std::make_pair(ope[i][0],ope[i][1]);
            f[i]=ma[f[i-1]][y];
            if(!f[i]) ma[f[i-1]][y]=i,push(f[i-1],i),f[i]=i;
        }
        else{
            f[i]=f[x];
        }
    }
    dfs(0,-1);
    for(int i=1;i<=n;i++)write(fin[f[i]]%P),putchar('\n');
}