专栏文章

题解：P13960 [ICPC 2023 Nanjing R] 后缀结构

__lbw_malerlee
P13960题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintj3ic
此快照首次捕获于
2025/12/02 08:06
3 个月前
此快照最后确认于
2025/12/02 08:06
3 个月前
查看原文
先建出 trie 树的 AC 自动机。
很明显问题的答案等价于对每个位置在 AC 自动机上沿 tt 走一遍，走 ii 个字符就给 gig_i 贡献上当前长度。
根据经典套路，我们不能直接维护所有点加一个字符会怎么变化，而是要对于一个点考虑什么时候无法转移跳 fail 了，再把贡献给到 fail 那个点。
具体而言，对于每个点预处理从这个点开始跟 tt 匹配的最长长度。
这一部分不好处理，因为各种均摊复杂度对的做法都不能搬到树上，我们考虑建出 tt 的 KMP 自动机，然后在 trie 树上跑出每个位置的最长匹配，那么会产生一个 Border 的有效贡献。
我们要对一个长度减去一个串的所有 Border checkmax，只能考虑 Border 理论了！
把 Border 划分成 log⁡\log 段 ABiAB^i，每一段除去最开头的串剩下的下一个字符都是 B1B_1 这个字符，那么他们下一个字符的可匹配性是相同的，只要判断当前节点有无 B1B_1 这条出边即可。
如果一个节点有 B1B_1 这条出边，那么这次贡献会被后一个点的贡献取代，而如果没有则这是这个点最后一次被更新，所以一个点只会被更新一次，加上第一段字符 log⁡\log 次贡献，总复杂度 1log。
然后我们考虑传给 fail 的贡献，很明显如果一直上传次数是 O(n)O(n) 的，但我们可以对每个节点记录一个数组 vu,iv_{u,i} 表示这个点 uu 还要给 gi∼gng_i\sim g_n 做 vu,iv_{u,i} 的贡献。
那么直接记录数组复杂度当然还是错的，但是我们发现这个过程如果直接用线段树合并记录复杂度就是对的了。
不过为什么我们要记录这个信息呢，其实是要把每个点给 gg 传递一串贡献。
而贡献的过程其实是把能匹配的点算了，无法匹配往上传，对应到 vv 上是把一串前缀做一次贡献，然后全部合并到前缀后一个点。
看起来很难做，但实际上可以暴力把前缀拿出来，因为拿出来过后会被合并成一个点，均摊就是对的了。
时间复杂度 O((n+m)log⁡n)O((n+m)\log n)。
CPP
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define I ll
#define her1 20081214
#define IV void
#define cht 1000000007
#define ld long double
#define Aestas16 392699
#define ull unsigned long long
#define cp(x,y)memcpy(x,y,sizeof y)
#define mem(x,mp)memset(x,mp,sizeof x)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
//#define D(i,j,n)for(int i=j;i>=n;i--)
//#define E(i,now)for(int i=first[now];i;i=e[i].nxt)
//#define F(i,j,n)for(int i=j;i<=n;i++)
//#define DL(i,j,n)for(register ll i=j;i>=n;i--)
//#define EL(i,now)for(register ll i=first[now];i;i=e[i].nxt)
//#define FL(i,j,n)for(register ll i=j;i<=n;i++)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
#undef ll
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
using i64 = long long;
const int maxn = 2e5+5;

IV cmax(i64&x,i64 val){x<val?x=val,0:0;}
map<i64,i64>ch[maxn];vector<pair<i64,i64> >e[maxn];
i64 n,m,p[maxn],dep[maxn],rt[maxn],fail[maxn],tot;

#define ls(o) xds[o].ls
#define rs(o) xds[o].rs
#define val(o) xds[o].val
struct node{i64 ls,rs,val;}xds[maxn*45];
IV M(i64&o,i64 l,i64 r,i64 p,i64 v){
	xds[++tot]=xds[o];o=tot;if(l==r)return(void)(val(o)=v);
	i64 mid=l+r>>1;p<=mid?M(ls(o),l,mid,p,v):M(rs(o),mid+1,r,p,v);
}
i64 Q(i64 o,i64 l,i64 r,i64 p){
	if(l==r)return val(o);i64 mid=l+r>>1;
	return p<=mid?Q(ls(o),l,mid,p):Q(rs(o),mid+1,r,p);
}
i64 nxt(i64 u,i64 c){return Q(rt[u],1,n,c);}
IV Build(){
	queue<i64>qwq;
	for(auto[v,c]:e[0])
		M(rt[0],1,n,c,v),qwq.push(v);
	while(!qwq.empty()){
		i64 u=qwq.front();qwq.pop();rt[u]=rt[fail[u]];
		for(auto[v,c]:e[u]){
			M(rt[u],1,n,c,v);
			fail[v]=nxt(fail[u],c);qwq.push(v);
		}
	}
}

i64 t[maxn],Bd[maxn],rt2[maxn];
i64 nxt2(i64 u,i64 c){
	return Q(rt2[u],1,n,c);
}
i64 lst[maxn],slink[maxn];
IV KMP(){
	M(rt2[0],1,n,t[1],1);
	F(i,2,m){
		Bd[i]=nxt2(Bd[i-1],t[i]);
		rt2[i-1]=rt2[Bd[i-1]];
		M(rt2[i-1],1,n,t[i],i);
		slink[i]=i-Bd[i];
	}
	rt2[m]=rt2[Bd[m]];
	F(i,1,m){
		if(!Bd[i]||slink[Bd[i]]!=slink[i])
			lst[i]=i;
		else lst[i]=lst[Bd[i]];
	}
}

i64 mx[maxn],now[maxn],stk[maxn],top;
IV dfs(i64 u){
	stk[++top]=u;
	for(auto[v,c]:e[u])
		now[v]=nxt2(now[u],c),dfs(v);

	i64 o=now[u];
	while(o){
		cmax(mx[stk[top-o]],o);
		i64 p=lst[o];
		if(!ch[u].count(t[p+1])){
			while(o!=p){
				o=Bd[o];
				cmax(mx[stk[top-o]],o);
			}
		}
		o=Bd[p];
	}
	top--;
}
vector<i64>G[maxn];
map<i64,i64>mp[maxn];
i64 sum[maxn];
IV add(i64 l,i64 r,i64 v){
	sum[l]+=v;
	sum[r+1]-=v;
}
IV add(i64 l,i64 r,i64 v,i64 c){
	if(l<=r){
		add(l,l,c*(v+l));
		add(l+1,r,c);
		add(r+1,r+1,-c*(v+r));
	}
}
IV merge(i64 u,i64 v){
	if(mp[u].size()<mp[v].size())
		swap(mp[u],mp[v]);
	for(auto[x,c]:mp[v])
		mp[u][x]+=c;
}
IV dfs2(i64 u){
	for(i64 v:G[u]){
		dfs2(v);
		merge(u,v);
	}
	i64 sum=0;
	if(u){
		while(mp[u].size()&&mp[u].begin()->first<=mx[u]){
			auto[x,c]=*mp[u].begin();mp[u].erase(mp[u].begin());
			sum+=c;add(x,mx[u],dep[u],c);
		}
		if(sum)mp[u][mx[u]+1]+=sum;
	}
}
IV solve(){
	tot=0;
	n=read();m=read();
	F(i,0,m)sum[i]=0;
	F(i,0,n)fail[i]=mx[i]=now[i]=t[i]=Bd[i]=rt[i]=0;
	F(i,0,n)mp[i].clear(),ch[i].clear(),e[i].clear(),G[i].clear();
	F(i,1,n)p[i]=read(),dep[i]=dep[p[i]]+1;
	F(i,0,m)rt2[i]=0;
	F(i,1,n){
		i64 c=read();
		e[p[i]].push_back({i,c});
		ch[p[i]][c]=i;mp[i][1]=1;
	}
	F(i,1,m)t[i]=read();
	Build();
	KMP();
	dfs(0);
	F(i,1,n)
		G[fail[i]].push_back(i);
	dfs2(0);

	i64 now=0,cc=0;
	F(i,1,m)sum[i]+=sum[i-1];
	F(i,1,m)sum[i]+=sum[i-1];
	F(i,1,m){
		now=nxt(now,t[i]);cc+=mp[0][i];
		sum[i]+=cc*dep[now];
	}
	F(i,1,m)printf("%lld ",sum[i]);puts("");
}
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	i64 T=read();while(T--)solve();return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...