bzoj 3881 Divljak

Posted on | Views:

$AC$ 自动机 + 树上小技巧.

对所有的 $s$ 串建出 $AC$ 自动机以及 $fail$ 树.

$fail$ 树中的每个点都能表示一个串,并且在子树 $i$ 内的点,每个点表示的串都有节点 $i$ 对应的串作为后缀.

每次插入一个串 $p$ 时,就在 $AC$ 自动机上匹配它,匹配过程中经过的所有点都是 $p$ 的前缀,而子串可以看做是前缀的后缀,所以将经过的这些前缀都加上一种新颜色,询问时答案就是 $s_i$ 对应节点子树中所含颜色种类.

可以用 $dfs$ 序 + 树状数组进行维护,为了避免一种颜色贡献被算多次,每次染色时将所有需要染色的点按 $dfs$ 序排序,相邻的两个点权值 $+1$ ,它们的 $LCA$ 权值 $-1$ ,询问时直接询问子树内权值总和.

这样做是和构造虚树时的做法差不多的,正确性比较显然.

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e6+10,S=26;
int id[MAXN],ecnt=0,head[MAXN],to[MAXN],nx[MAXN];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int dfn[MAXN],dfnidx=0,top[MAXN],siz[MAXN],mxson[MAXN],dep[MAXN],fa[MAXN];
void dfs1(int u,int f)
{
	fa[u]=f;
	siz[u]=1;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==f)
			continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[mxson[u]])
			mxson[u]=v;	
	}
}
void dfs2(int u,int tp)
{
	dfn[u]=++dfnidx;
	top[u]=tp;
	if(mxson[u])
		dfs2(mxson[u],tp);
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa[u] || v==mxson[u])
			continue;
		dfs2(v,v);
	}
}
int LCA(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<=dep[y]?x:y;
}
struct FenwickTree
{
	int bit[MAXN];
#define lowbit(x) x&(-x)
	void add(int x,int c)
	{
		for(;x<=dfnidx;x+=lowbit(x))
			bit[x]+=c;
	}	
	int sum(int x)
	{
		int s=0;
		for(;x;x-=lowbit(x))
			s+=bit[x];
		return s;
	}
}T;
char s[MAXN];
int len,tmp[MAXN],tot=0;
bool cmp(int x,int y)
{
	return dfn[x]<dfn[y];
}
struct AhoCorasick_Automaton
{
	int ch[MAXN][S],fail[MAXN],vis[MAXN],idx;
	AhoCorasick_Automaton(){idx=1;}
	void ins(int x)
	{
		int u=1;
		for(int i=1;i<=len;++i)
		{
			int c=s[i]-'a';
			if(!ch[u][c])
				ch[u][c]=++idx;
			u=ch[u][c];
		}
		id[x]=u;
	}
	void getfail()
	{
		queue<int> q;
		q.push(1);
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			for(int i=0;i<S;++i)
				if(ch[u][i])
				{
					int v=ch[u][i];
					q.push(v);
					int f=fail[u];
					while(f && ch[f][i]==0)
						f=fail[f];
					if(f)
						fail[v]=ch[f][i];
					else
						fail[v]=1;
					addedge(fail[v],v);
				}
		}
	}
	void match()
	{
		int u=1;
		tot=0;
		for(int i=1;i<=len;++i)
		{
			int c=s[i]-'a';
			if(ch[u][c])
				u=ch[u][c];
			else
			{
				while(u && ch[u][c]==0)
					u=fail[u];
				if(ch[u][c])
					u=ch[u][c];
				else
					u=1;
			}
			tmp[++tot]=u;
			T.add(dfn[u],1);
		}
		sort(tmp+1,tmp+1+tot,cmp);
		for(int i=1;i<tot;++i)
			T.add(dfn[LCA(tmp[i],tmp[i+1])],-1);
	}
	int query(int x)
	{
		return T.sum(dfn[x]+siz[x]-1)-T.sum(dfn[x]-1);
	}
}AC;
int main()
{
	int n=read();
	for(int i=1;i<=n;++i)
	{
		scanf("%s",s+1);
		len=strlen(s+1);
		AC.ins(i);
	}
	AC.getfail();
	dfs1(1,0);
	dfs2(1,1);
	int m=read();
	for(int i=1;i<=m;++i)
	{
		int op=read();
		if(op==1)
		{
			scanf("%s",s+1);
			len=strlen(s+1);
			AC.match();
		}
		else
		{
			int x=read();
			printf("%d\n",AC.query(id[x]));
		}	
	}
	return 0;
}