你需要动态维护一个字符串 ,有 次操作:
1 x c
:在 末尾加上 个字符 ,保证操作前 末尾字符不为 ;2 x
:撤销第 次操作后的所有操作;输出每次操作结束 的每个前缀的最长真 Border 的长度的和。
,。
首先可持久化可以通过在操作树上 dfs 干掉,那么我们需要一个非均摊的东西来维护答案。
由于相邻 操作的 不同,所以 可以被划分成若干段,每次操作就相当于在末尾加入一段。
考虑维护 的最长真 Border,不妨用二元组 表示一段。对于 的一个 Border,不难发现前缀的 和后缀的 除了开头结尾外都要完全一致,而:
- 若开头不一致,则之后插入时肯定不能继承这个 Border,所以这个 Border 没用;
- 若结尾不一致,一定是后缀的 大于前缀的 ,否则同样没用;
也就是说,有用的 Border 的前缀肯定包含完整的段。
那么不妨维护二元组序列,用 表示前缀 的最长有用真 Border 包含的二元组的个数。
有了 ,一个暴力的想法是:直接跳 ,假设当前插入的第 个二元组为 ,则维护一个指针 表示已经算出了当前段 的极长真 Border 的长度,跳到一个 Border 时假设第 个二元组是 且 ,则:
- 若 则答案加上一个等差数列,更新 ,停止跳 ;
- 否则若 则答案加上一个等差数列,更新 ;
最后还要特判一下 且 不被真 Border 完全包含的情况。
这样暴力跳是均摊 的,操作树来个菊花就卡死了。
继续利用相邻二元组 不同的性质,对于一个 的 Border , 必然是一个 Period,并且这些 的 Border 构成一个等差数列,所以对于每个 的 Border ,第 个二元组必然相同。由于相邻二元组 不同,所以 的 Border 都被它们中最长的那个支配,那么处理完最长那个后直接跳过剩下的即可。
根据经典结论,这样的等差数列只会有 个,那么就做完了,时间复杂度 。
代码如下:
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int S=100005,p=998244353;
struct node
{
int x,c;
};
int n,m,rt[S];
vector<pair<int,node> > g[S];
vector<int> idx[S];
int tot;
node a[S];
int len[S],fail[S];
int ans[S];
inline void add(int &x,int y)
{
x+=y;
if(x>=p) x-=p;
}
inline int ins(node x)
{
a[++tot]=x;
len[tot]=(len[tot-1]+x.x)%p;
if(tot==1)
{
fail[tot]=0;
return 1ll*(x.x-1)*x.x/2%p;
}
int res=0;
fail[tot]=0;
int cur=0,n=tot-1,u=fail[tot-1];
while(1)
{
if(a[u+1].c==x.c)
{
if(a[u+1].x==x.x)
{
int lft=x.x-cur;
add(res,1ll*(cur+1+x.x)*lft/2%p);
add(res,1ll*len[u]*lft%p);
fail[tot]=u+1;
break;
}
else if(a[u+1].x>cur)
{
int le=min(x.x,a[u+1].x),lft=le-cur;
add(res,1ll*(cur+1+le)*lft/2%p);
add(res,1ll*len[u]*lft%p);
cur=le;
}
if(u==0&&a[1].x<x.x)
{
int lft=x.x-cur;
add(res,1ll*a[1].x*lft%p);
fail[tot]=1;
break;
}
}
if(u==0) break;
if(u>n/2)
{
int len=n-u,lft=u-n/2;
u=u-(lft/len+(lft%len!=0))*len+len;
n=u,u=fail[u];
}
else n=u,u=fail[u];
}
return res;
}
void dfs(int u,int res)
{
for(int id:idx[u]) ans[id]=res;
for(auto t:g[u])
{
int v=t.first;
node x=t.second;
int tt=tot;
dfs(v,(res+ins(x))%p);
tot=tt;
}
}
int main()
{
scanf("%d",&n);
rt[0]=m=1;
for(int i=1;i<=n;i++)
{
int op,x;
scanf("%d%d",&op,&x);
if(op==1)
{
char c;
scanf(" %c",&c);
g[rt[i-1]].emplace_back(rt[i]=++m,(node){x,c-'a'+1});
}
else rt[i]=rt[x];
idx[rt[i]].push_back(i);
}
dfs(rt[0],0);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}