Kruskal重构树+AC自动机+树状数组：Gym - 104542F

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818179

https://vjudge.net/contest/579844#problem/F

  1. 看到连边和没有强制在线，考虑Kruskal重构树

  2. 看到判断子串，考虑AC自动机+线段树

然后要非常大胆地把两个结合起来。

然后就是大码量了。

具体总结一下流程：

  1. 先建出Kruskal重构树

  2. 对Kruskal重构树处理出dfn序

  3. 重新对字符串进行排序

  4. 对字符串建AC自动机

  5. 对fail树处理出dfn序

  6. 对询问操作处理出Kruskal重构树上对应区间进行差分

  7. 按顺序加入每个字符串，在树状数组上进行区间加操作，树状数组维护差分

  8. 对于每个询问在Trie树上跑，在对应树状数组上询问并统计答案

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define N 500010
struct node {
	int id, f; 
};
int n, m, i, j, k, T;
int a[N], a_st[N], a_ed[N], num, tot; 
int dfn[N], ed[N], p[N], qqq, f[N], op, dian[N]; 
int ans[N]; 
int u, v; 
vector<int>G[N]; 
vector<node>Q[N]; 
vector<int>s[N], t[N], S[N]; 
char str[N]; 
queue<int>q; 

int fa(int x) {
	if(f[x]==x) return x; 
	return f[x]=fa(f[x]); 
}

void dfs(int x) {
	if(x<=n) a[++num]=x, a_st[x]=num; 
	for(int y :  G[x]) {
		dfs(y); 
		if(!a_st[x]) a_st[x]=a_st[y]; 
	}
	a_ed[x]=num; 
}

struct Tree_zhuang_number_group {
	int n, cnt[N]; 
	void add(int x, int y) {
		while(x<=n)	 {
			cnt[x]+=y; x+=x&-x; 
		}
	}
	int que(int x) {
		int ans=0; 
		while(x) ans+=cnt[x], x-=x&-x; 
		return ans; 
	}
}Bin;

struct AC_auto_machine {
	int tot=1, nxt[N][26], fail[N]; 
	int dfn[N], ed[N], num; 
	vector<int>G[N]; 
	int Trie(int u, int i, int id) {
		if(!s[id][i]) return u; 
		int c=s[id][i]-'a'; 
		if(!nxt[u][c]) nxt[u][c]=++tot; 
		return Trie(nxt[u][c], i+1, id); 
	}
	void bfs() {
		q.push(1); 
		while(!q.empty()) {
			u=q.front(); q.pop(); 
			for(int i=0; i<26; ++i) {
				if(!nxt[u][i]) continue; 
				v=nxt[u][i]; k=fail[u]; 
				while(k && !nxt[k][i]) k=fail[k]; 
				if(nxt[k][i]) fail[v]=nxt[k][i]; 
				else fail[v]=1; 
				q.push(v); 
			}
		}
	}
	void pre_dfs() {
		for(int i=2; i<=tot; ++i) G[fail[i]].pb(i); 
	}
	void dfs(int x) {
		dfn[x]=++num;
		for(int y : G[x]) dfs(y); 
		ed[x]=num; 
	}
	void jia(int i) {
		Bin.add(ed[p[i]]+1, -1); 
		Bin.add(dfn[p[i]], 1); 
	}
	int que(int id) {
		char c; 
		int ans=0; 
		for(int j=1, i=0; t[id][i]; ++i) {
			c=t[id][i]-'a'; 
			while(j && !nxt[j][c]) j=fail[j]; 
			if(nxt[j][c]) j=nxt[j][c]; 
			else j=1; 
			ans+=Bin.que(dfn[j]); 
		}
		return ans; 
	}
}AC;

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	n=read(); 
	for(i=1; i<=n; ++i) {
		scanf("%s", str+1); 
		for(j=1; str[j]; ++j) S[i].pb(str[j]); S[i].pb(0); 
	}
	qqq=read(); tot=n; 
	for(i=1; i<=2*n; ++i) f[i]=i; 
	while(qqq--) {
		op=read(); 
		if(op==1) {
			u=read(); v=read(); 
			u=fa(u); v=fa(v); 
			if(u==v) continue; 
			++tot; G[tot].pb(u); G[tot].pb(v); 
			f[u]=tot; f[v]=tot; 
		}
		else {
			u=read(); scanf("%s", str+1); 
			u=fa(u); 
			++m; dian[m]=u; 
			for(j=1; str[j]; ++j) t[m].pb(str[j]); t[m].pb(0); 
		}
	} 
	for(i=1; i<=tot; ++i) if(fa(i)==i) G[tot+1].pb(i), f[i]=tot+1; 
	++tot; 
	dfs(tot); 
	for(i=1; i<=n; ++i) s[i]=S[a[i]]; 
	for(i=1; i<=n; ++i) {
		p[i]=AC.Trie(1, 0, i); 
	}
	AC.bfs(); 
	AC.pre_dfs(); 	
	AC.dfs(1); 
	Bin.n=AC.tot; 
	for(i=1; i<=m; ++i) {
		Q[a_st[dian[i]]-1].pb({i, -1}); 
		Q[a_ed[dian[i]]].pb({i, 1}); 
	}
	for(i=1; i<=n; ++i) {
		AC.jia(i);
		for(node x : Q[i]) {
			ans[x.id]+=x.f*AC.que(x.id); 
		}
	}
	for(i=1; i<=m; ++i) printf("%lld\n", ans[i]); 
	return 0;
}

``