[百紫祭] 洛谷P5840做题笔记
前置芝士：AC自动机，树上差分，树剖求LCA，树状数组。
前言
一篇笔记需要一张头图。
题意
给出 \(n\) 个字符串 \(S_1，S_2\ .\ .\ .\ S_n\) 和一个初始为空的字符串集合 \(T\) ，接下来 \(q\) 次操作。操作分为修改和询问。
修改操作为向 \(T\) 中插入一个字符串 \(P\) ；查询操作为求出 \(T\) 中有多少个包含了 \(S_x\) 。对每个查询输出答案。
题解
一道AC自动机的神题，值得一做。
看到 “字符串” ，“包含” 两个字眼，可以想到一种很暴力的AC自动机做法。
具体做法是：每插入一个字符串 \(P\) ，考虑暴力跳fail指针求出所有其包含的字符串，将所有包含的字符串答案加一。查询时只要输出就行。
但是看到 \(2 \times 10^6\) 的数据范围，显然是会炸的。考虑优化。
比较主流的做法是在AC自动机上做树上差分+树剖LCA+树状数组。
考虑记录 \(P\) 在AC自动机上跳到过的所有点。学过AC自动机的都知道，AC自动机上跳到的每一个点所代表的字符串都包含在 \(P\) 内。
然后我们观察跳fail指针的过程。众所周知AC自动机的fail可以构成一棵树，那么一次更新答案就是将根节点到当前跳到的节点链上的所有点加一。
可以考虑一种思路，先求出所有点的 \(dfs\) 序，方便后续操作。
设 \(P\) 串在匹配过程中跳到了 \(u_1，u_2，u_3\ .\ . \ .\ u_l\)，那么我们可以完成以下操作：
1：根据所有点的 \(dfs\) 序排序
2：对于每个节点，将 \(u_i\) 到根节点链上所有点加一。
3：对于每个点对 \((u_i，u_{i+1})\) ，将 \(LCA(u_i，u_{i+1})\) 到根节点上链上的所有点减一。（因为不能重复算。）
对于 \(LCA\) ，显然可以树链剖分求。（注：笔者尝试倍增LCA结果貌似被卡，所以临时学了更快的树剖LCA，可以顺利通过）对于链上操作，显然可以使用树上差分。那么2，3操作就可以转换成单点操作。
但是查询就又要讨论了。使用了树上差分后，查询操作从单点查变成了求子树和。
这时候前面处理的 \(dfs\) 序再次派上用场了。根据 \(dfs\) 序的性质，一个子树内所有的编号是连续的。这时候就可以用一波树状数组了。
总结一下思路，第一步建AC自动机，第二步在AC自动机上 \(dfs\) 求出 \(dfs\) 序，并预处理树剖 \(LCA\) 。第三步结合树上差分和树状数组进行修改和查询。
总复杂度 \(O(|S|\ log\ |S|)\) ，对于四秒而言已经足够。
code
//writer:Oier_szc
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+5,M=2e6+5;
int n;
char s[N];
int tr[M][26],idx=0;
int fail[M],id[N];
inline void insert(int ID,char s[])
{
int u=0;
for(int i=1;i<=strlen(s+1);++i)
{
int to=s[i]-'a';
if(!tr[u][to]) tr[u][to]=++idx;
u=tr[u][to];
}
id[ID]=u;
}
inline void build()
{
queue<int> q;
for(int i=0;i<26;++i)
{
if(tr[0][i]) q.push(tr[0][i]);
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<26;++i)
{
if(!tr[now][i])
{
tr[now][i]=tr[fail[now]][i];
}
else
{
fail[tr[now][i]]=tr[fail[now]][i];
q.push(tr[now][i]);
}
}
}
}
int head[M],ne[M<<1],to[M<<1],tot=0;
inline void add(int u,int v)
{
to[++tot]=v;
ne[tot]=head[u];
head[u]=tot;
}
int dfn[M],r[M],timec=0;
int top[M],son[M],sz[M],fa[M],deep[M];
inline void dfs(int u)
{
dfn[u]=r[u]=++timec;
sz[u]=1;
for(int i=head[u];i;i=ne[i])
{
fa[to[i]]=u;
deep[to[i]]=deep[u]+1;
dfs(to[i]);
sz[u]+=sz[to[i]];
if(!son[u]||sz[to[i]]>sz[son[u]]) son[u]=to[i];
//!son[u]必须加，不然u==0肯定出问题，T飞掉。
r[u]=max(r[u],r[to[i]]);
}
}
inline void dfs2(int u,int Top)
{
top[u]=Top;
if(son[u]) dfs2(son[u],Top);
for(int i=head[u];i;i=ne[i])
{
if(to[i]==son[u]) continue;
dfs2(to[i],to[i]);
}
}
inline int lca(int a,int b)
{
while(top[a]!=top[b])
{
if(deep[top[a]]>deep[top[b]]) a=fa[top[a]];
else b=fa[top[b]];
}
return deep[a]<deep[b]?a:b;
}
int tree[M];
int v[M];
inline int lowbit(int u)
{
return u&(-u);
}
inline void update(int u,int x)
{
for(int i=u;i<=timec;i+=lowbit(i))
{
tree[i]+=x;
}
}
inline int query(int u)
{
int res=0;
for(int i=u;i!=0;i-=lowbit(i))
{
res+=tree[i];
}
return res;
}
inline bool cmp(int a,int b)
{
return dfn[a]<dfn[b];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%s",s+1);
insert(i,s);
}
build();
for(int i=1;i<=idx;++i)
{
add(fail[i],i);
}
dfs(0);
dfs2(0,0);
int q;
scanf("%d",&q);
int op,x;
while(q--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%s",s+1);
int p=0;
int len=strlen(s+1);
for(int i=1;i<=len;++i)
{
int to=s[i]-'a';
p=tr[p][to];
v[i]=p;
}
sort(v+1,v+1+len,cmp);
for(int i=1;i<=len;++i)
{
update(dfn[v[i]],1);
}
for(int i=1;i<=len-1;++i)
{
update(dfn[lca(v[i],v[i+1])],-1);
}
}
else
{
scanf("%d",&x);
printf("%d\n",query(r[id[x]])-query(dfn[id[x]]-1));
}
}
return 0;
}