题解 P5287 【[HNOI2019]JOJO】
Isonan
2019-04-09 21:01:54
（此题考查了对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)$
（如有错误请不吝赐教）
代码：
```cpp
// 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');
}
```