P5287 [HNOI2019] JOJO 做题记录

你需要动态维护一个字符串 $S$，有 $n$ 次操作：

• 1 x c：在 $S$ 末尾加上 $x$ 个字符 $c$，保证操作前 $S$ 末尾字符不为 $c$；
• 2 x：撤销第 $x$ 次操作后的所有操作；

输出每次操作结束 $S$ 的每个前缀的最长真 Border 的长度的和。

$1\le n\le 10^5$，$1\le x\le 10^4$。

首先可持久化可以通过在操作树上 dfs 干掉，那么我们需要一个非均摊的东西来维护答案。

由于相邻 $1$ 操作的 $c$ 不同，所以 $S$ 可以被划分成若干段，每次操作就相当于在末尾加入一段。

考虑维护 $S$ 的最长真 Border，不妨用二元组 $(x,c)$ 表示一段。对于 $S$ 的一个 Border，不难发现前缀的 $(x,c)$ 和后缀的 $(x,c)$ 除了开头结尾外都要完全一致，而：

• 若开头不一致，则之后插入时肯定不能继承这个 Border，所以这个 Border 没用；
• 若结尾不一致，一定是后缀的 $x$ 大于前缀的 $x$，否则同样没用；

也就是说，有用的 Border 的前缀肯定包含完整的段。

那么不妨维护二元组序列，用 $fail_u$ 表示前缀 $u$ 的最长有用真 Border 包含的二元组的个数。

有了 $fail$，一个暴力的想法是：直接跳 $fail$，假设当前插入的第 $t$ 个二元组为 $(x,c)$，则维护一个指针 $cur$ 表示已经算出了当前段 $[1,cur]$ 的极长真 Border 的长度，跳到一个 Border $i$ 时假设第 $i+1$ 个二元组是 $(y,c’)$ 且 $c=c'$，则：

• 若 $x=y$ 则答案加上一个等差数列，更新 $fail_{t}=i+1$，停止跳 $fail$；
• 否则若 $y>cur$ 则答案加上一个等差数列，更新 $cur=\min\{x,y\}$；

最后还要特判一下 $fail_t=1$ 且 $(x,c)$ 不被真 Border 完全包含的情况。

这样暴力跳是均摊 $O(n)$ 的，操作树来个菊花就卡死了。

继续利用相邻二元组 $c$ 不同的性质，对于一个 $>\lfloor\frac{n}{2}\rfloor$ 的 Border $k$，$n-k$ 必然是一个 Period，并且这些 $>\lfloor\frac{n}{2}\rfloor$ 的 Border 构成一个等差数列，所以对于每个 $>\lfloor\frac{n}{2}\rfloor$ 的 Border $k$，第 $k+1$ 个二元组必然相同。由于相邻二元组 $c$ 不同，所以 $>\lfloor\frac{n}{2}\rfloor$ 的 Border 都被它们中最长的那个支配，那么处理完最长那个后直接跳过剩下的即可。

根据经典结论，这样的等差数列只会有 $O(\log n)$ 个，那么就做完了，时间复杂度 $O(n\log n)$。

代码如下：

#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;
}