CF710F String Set Queries

, ,

Description

https://www.luogu.com.cn/problem/CF710F

注意强制在线。

Solution

做之前的我的想法是对长度相同的暴力。根据经典结论长度的种类数只有 $\sqrt{\sum|S|}$ 种。然后暴力哈希就好了。

但是感觉很不优美啊，于是就向方队问了一发。

还是要结合 AC 自动机。但是每次重构就还不如暴力。于是我们用二进制分组的思想，加入一个串，如果这个 AC 自动机维护串的个数等于前一个就暴力合并。这样就是形如二进制分组一样。

每个串最多会被重构 $O(\log n)$ 次。查询的复杂度就是组数也是 $O(\log n)$。

怕被卡空间，还写了个垃圾回收。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 600005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n;
struct node {
	int l,r,root;
}g[maxn];
int rnums;
string ts[maxn];
struct yyy {
	int nex[26],vis[26],fail,val;
}a[maxn];
int tot,cnt,w[maxn],stac[maxn];
int clone() {
	int now=0;
	if (tot) now=stac[tot--];
	else now=++cnt;
	for (int i=0;i<26;i++) a[now].nex[i]=a[now].vis[i]=0;
	a[now].fail=a[now].val=0;
	return now;
}
void insert(int root,string s,int fl) {
	int now=root,len=s.size(),i;
	for (i=0;i<len;i++) {
		if (!a[now].nex[s[i]-'a']) a[now].nex[s[i]-'a']=clone(),a[now].vis[s[i]-'a']=1;
		now=a[now].nex[s[i]-'a'];
	}
	a[now].val+=fl;
} 
void clear(int x) {
	stac[++tot]=x;int i;
	for (i=0;i<26;i++) if (a[x].vis[i]) {
		clear(a[x].nex[i]);a[x].nex[i]=0;
	}
}
queue<int>q;
void build(int root) {
	int i,x;
	for (i=0;i<26;i++)
		if (a[root].nex[i]) a[a[root].nex[i]].fail=root,q.push(a[root].nex[i]);
		else a[root].nex[i]=root;
	while (!q.empty()) {
		x=q.front();q.pop();
//		gdb(a[x].val,x);
		a[x].val+=a[a[x].fail].val;
		for (i=0;i<26;i++) 
			if (a[x].nex[i]) a[a[x].nex[i]].fail=a[a[x].fail].nex[i],q.push(a[x].nex[i]);
			else a[x].nex[i]=a[a[x].fail].nex[i]; 
	}
}
int query(int root,string s) {
	int i,len=s.size(),x=root;
	ll ans=0;
	for (i=0;i<len;i++) {
		x=a[x].nex[s[i]-'a'];
		ans+=a[x].val;
//		gdb(x,a[x].val); 
	}
	return ans;
}
signed main(void){
	freopen("1.in","r",stdin);
	int i,j,op,T,times=0;string s;
	read(T);
	while (T--) {
		read(op);cin>>s;
		if (op<=2) {
			int fl=(op==1?1:-1);
			++times;w[times]=fl;ts[times]=s;
			++rnums;g[rnums].l=g[rnums].r=times,g[rnums].root=clone();
			insert(g[rnums].root,ts[times],w[times]);
			build(g[rnums].root);
			for (i=rnums;i>=2;i--) 
				if (g[i].r-g[i].l==g[i-1].r-g[i-1].l) {
					clear(g[i].root),clear(g[i-1].root);
					g[i-1].root=clone();
					for (j=g[i-1].l;j<=g[i].r;j++) insert(g[i-1].root,ts[j],w[j]);
					build(g[i-1].root);g[i-1].r=g[i].r;
//					gdb("build",g[i-1].l,g[i-1].r);
					rnums--;
				}
		}
		else {
			ll ans=0;
			for (i=1;i<=rnums;i++) ans+=query(g[i].root,s);
			printf("%lld\n",ans);
			fflush(stdout);
		}
	}	
	return 0;
}