[SDOI2016]生成魔咒 简易题解

发表于 更新于 分类于

题目传送门：[SDOI2016]生成魔咒

想法

引入

$\ \ \ \ \ \ \,$一看这个题目：

  • 只是单调在后面加字符；
  • 只是统计子串数量。

$\ \ \ \ \ \ \,$哇！这不是 $SAM$ 的裸题吗，周道感动得要哭了，根据【后缀自动机的性质】：

解法

$\ \ \ \ \ \ \,$点$i$上面表示子串的数量为:$len[fa[i]]−len[i]$
$\ \ \ \ \ \ \,$所以我们每次插入一个点，把新加的子串个数记累加就好了。

$\ \ \ \ \ \ \,$但是一看这个字符集大小……

$\ \ \ \ \ \ \,$不过我们知道，虽然字符集这么大，但是每个节点上面的儿子个数却是远远达不到字符集那么大的，所以我们试着用 $map$ 代替数组来记录儿子：

$\ \ \ \ \ \ \,$然后……就过了……

代码

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
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
	int x=0,f=1;char ch;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
	if(f)return x;else return -x;
}
const int N=200010;
long long ans; 
struct Suffix_Automaton{
	map<int,int>ch[N];
  	int last=1,cnt=1;
	int len[N],fa[N];
	void insert(int c){
		int np=++cnt,p=last;last=np;
		len[np]=len[p]+1;
		for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
		if(!p)fa[np]=1;
		else{
			int q=ch[p][c];
			if(len[q]==len[p]+1)fa[np]=q;
			else{
				int nq=++cnt;len[nq]=len[p]+1;
				ch[nq]=ch[q];
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
			}
		}
		ans+=1ll*len[np]-len[fa[np]];
	}
}Sam;
int main()
{
	int n=read();
	while(n--){
		int a=read();
		Sam.insert(a);
		printf("%lld\n",ans);
	}
	return 0;
}