【FAIL树+dfs序】Divljak

字符串, 树论

传送门：BZOJ3881

先BB了个后缀树+树剖+线段树乱搞的做法，然后发现只因为我不会求LCA

思路：

  • 把模式串建成AC自动机，然后每次加入询问串时就更新答案；
  • 更新时把所有匹配点+1，LCA-1；
  • LCA似乎可以按dfs序排序以后求（我居然不会这种操作）；
  • 发现每个状态的答案实际是FAIL树上子树求和；
  • 树剖LCA吊锤RMQ？
  • 似乎会求LCA后缀树也能直接搞？

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
#define N 2200000
int n,m,cnt,x,op,clk,tot,p,sz[N],fst[N],end[N],dfn[N],top[N],deep[N];
int head[N],c[N][30],fa[N],q[N],bit[N],pos[N],t[N];
char s[N];
struct edge{int v,nxt;}e[N];
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void mdf(int x,int k){
	for (int i=x;i<=p;i+=i&(-i)) bit[i]+=k;
}
int qry(int x){
	int ret=0;
	for (int i=x;i;i-=i&(-i)) ret+=bit[i];
	return ret;
}
void dfs1(int u){
	fst[u]=end[u]=dfn[u]=++clk; deep[u]=deep[fa[u]]+1; sz[u]=1;
	for (int i=head[u],v;i;i=e[i].nxt){
		dfs1(v=e[i].v); end[u]=end[v]; sz[u]+=sz[v];
	}
}
void dfs2(int u){
	if (!top[u]) top[u]=u; int t=0;
	for (int i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa[u]&&sz[v]>sz[t]) t=v;
	if (!t) return; top[t]=top[u]; dfs2(t);
	for (int i=head[u],v;i;i=e[i].nxt)
		if ((v=e[i].v)!=fa[u]&&v!=t) dfs2(v);
}
int lca(int u,int v){
	for (;top[u]!=top[v];u=fa[top[u]]) if (deep[top[u]]<deep[top[v]]) swap(u,v);
	return deep[u]<deep[v]?u:v;
}
	
int main(){
	scanf("%d",&n); cnt=1;
	for (int i=1;i<=n;i++){
		scanf("%s",s+1);
		int xb=1,len=strlen(s+1); p+=len;
		for (int j=1;j<=len;j++){
			int w=s[j]-'a';
			if (!c[xb][w]) c[xb][w]=++cnt;
			xb=c[xb][w];
		}
		pos[i]=xb;
	}
	int tt=0,ww=1; q[1]=1;
	while (tt<ww){
		int xb=q[++tt];
		add(fa[xb],xb);
		for (int i=0;i<26;i++) if (c[xb][i]){
			if (xb){
				int tmp=fa[xb];
				while (tmp&&!c[tmp][i]) tmp=fa[tmp];
				if (tmp) fa[c[xb][i]]=c[tmp][i];
				else fa[c[xb][i]]=1;
			}
			q[++ww]=c[xb][i];
		}
	}
	dfs1(1); dfs2(1);
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d",&op);
		if (op==1){
			scanf("%s",s+1);
			int xb=1,len=strlen(s+1),tmp=0;
			for (int j=1;j<=len;j++){
				int w=s[j]-'a';
				while (xb&&!c[xb][w]) xb=fa[xb];
				if (!xb) xb=1; else xb=c[xb][w];
				t[++tmp]=xb;
			}
			sort(t+1,t+tmp+1,cmp);
			mdf(dfn[t[1]],1);
			for (int j=2;j<=tmp;j++){
				mdf(dfn[t[j]],1);
				mdf(dfn[lca(t[j-1],t[j])],-1);
			}
		}
		else{
			scanf("%d",&x);
			printf("%d\n",qry(end[pos[x]])-qry(fst[pos[x]]-1));
		}
	}
	
	return 0;
}