P5287 [HNOI2019] JOJO 做题记录

你需要动态维护一个字符串 SS,有 nn 次操作:

  • 1 x c:在 SS 末尾加上 xx 个字符 cc,保证操作前 SS 末尾字符不为 cc
  • 2 x:撤销第 xx 次操作后的所有操作;

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

1n1051\le n\le 10^51x1041\le x\le 10^4

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

由于相邻 11 操作的 cc 不同,所以 SS 可以被划分成若干段,每次操作就相当于在末尾加入一段。

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

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

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

那么不妨维护二元组序列,用 failufail_u 表示前缀 uu 的最长有用真 Border 包含的二元组的个数。

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

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

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

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

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

根据经典结论,这样的等差数列只会有 O(logn)O(\log n) 个,那么就做完了,时间复杂度 O(nlogn)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;
}