题意：
初始有一个空串，有n次操作：
- $(1,x,c)$，表示在当前串后添加x个字符c，保证c不同于当前串末尾的字符。
- $(2,x)$，表示将当前串变成第x次操作后的串。
每次操作完你需要输出$sum limits_{i=1}^{n}{nxt(i)}$，其中$nxt(i)$与kmp中的nxt同义。
$nleq 10^{5},xleq 10^{4}$。
题解：
首先考虑怎么将普通kmp扩展到字符块的kmp。先假设没有2操作。
将每个块视作一个字符（二元组$(x,c)$）建一个新串，容易发现如果某段前缀和后缀这两个串相匹配，则满足
- 两个串的二元组个数相等。
- 两个串除了首尾其他二元组均相等。
- 后缀首位的x$geq$前缀首位的x，前缀末位的x$geq $后缀元素的x。
那么显然可以记$nxt'(i)$表示新串的nxt。两个$geq$不好处理，我们令$nxt'(i)$匹配的末位元素必须对位相等。
此时就可以仿照kmp的做法跳指针，并在跳的同时更新当前二元组的贡献（大概是不断取max做等差数列求和），就解决了没有2操作的问题。
考虑2操作，对于不强制在线的题目，有一个套路是把操作离线下来建成一棵树，dfs即可。
但kmp的复杂度是均摊的，上树直接做怕是不行，一条链底下挂个菊花就能把这个做法卡飞。
考虑优化，容易发现复杂度错误的时候这个串一定是一个循环串，而且x都相等不影响更新答案，那么每次直接跳到第一个循环节即可计算。
注意遇到一个循环串应该先跳一下nxt判断能不能匹配而不是直接跳到头，这样不符合nxt极大的性质。
其实也可以主席树维护kmp自动机做。但是我过了就不想写了。
复杂度$O(nlog{n})$，跳的时候注意边界。
套路：
- 遇到扩展问题$ ightarrow$想一下能不能用原问题的思路做。
- 不强制在线有撤回操作$ ightarrow$将操作离线建树dfs处理。
代码：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define mod 998244353 #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll siz[maxn],id[maxn],fa[maxn],res[maxn]; ll sum[maxn],nxt[maxn],ind[maxn]; vector<ll> to[maxn]; char ch[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void dfs(ll u,ll n){ if(n==0){for(rint i=0;i<to[u].size();i++){ll v=to[u][i];dfs(v,n+1);}return;} id[n]=u,sum[n]=sum[n-1]+siz[u],res[u]=res[fa[u]]; if(n==1){ nxt[n]=0; ll a1=0,an=siz[u]-1; res[u]+=(a1+an)*(an-a1+1)/2,res[u]%=mod; } else{ ll j=nxt[n-1],hv=0,len=n-1-j; while(j && ((ch[id[j+1]]!=ch[u])||(siz[id[j+1]]!=siz[u]))){ if(ch[id[j+1]]==ch[u] && siz[id[j+1]]>hv){ ll a1=sum[j]+hv+1,an=sum[j]+min(siz[id[j+1]],siz[u]); res[u]+=(a1+an)*(an-a1+1)/2,res[u]%=mod,hv=min(siz[id[j+1]],siz[u]); } if(j-nxt[j]==len) j=j-nxt[j]; len=j-nxt[j],j=nxt[j]; } if(ch[id[j+1]]!=ch[u]) nxt[n]=0; else{ if(siz[id[j+1]]<=siz[u]){ nxt[n]=j+1; ll a1=sum[j]+hv+1,an=sum[j+1]; res[u]+=(a1+an)*(an-a1+1)/2,res[u]%=mod; res[u]+=(siz[u]-siz[id[j+1]])*sum[j+1],res[u]%=mod; } else{ nxt[n]=0; ll a1=hv+1,an=siz[u]; res[u]+=(a1+an)*(an-a1+1)/2,res[u]%=mod; } } } for(rint i=0;i<to[u].size();i++){ll v=to[u][i];dfs(v,n+1);} } int main(){ //freopen("jojo7.in","r",stdin); //freopen("1.out","w",stdout); ll n=read(); for(rint i=1;i<=n;i++){ ll op=read(); if(op==1) fa[i]=ind[i-1],ind[i]=i,siz[i]=read(),scanf("%c",&ch[i]); else{ll x=read();ind[i]=ind[x];} } for(rint i=1;i<=n;i++) if(ind[i]==i) to[fa[i]].push_back(i); for(rint i=0;i<=n;i++) if(to[i].size()) sort(to[i].begin(),to[i].end()); dfs(0,0); for(rint i=1;i<=n;i++) printf("%lld ",res[ind[i]]); return 0; }