生成魔咒
Time Limit: 10 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]
Description
魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。
一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。
例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。
S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种。
最初 S 为空串。共进行 n 次操作，每次操作是在 S 的结尾加入一个魔咒字符。
每次操作后都需要求出，当前的魔咒串 S 共有多少种生成魔咒。
Input
第一行一个整数 n。
第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。
Output
输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量
Sample Input
7
1 2 3 3 3 1 2
1 2 3 3 3 1 2
Sample Output
1
3
6
9
12
17
22
3
6
9
12
17
22
HINT
1≤n≤100000
Main idea
询问在加入每一个字符后当前有多少个本质不同的子串。
Solution
直接用SAM，根据SAM的性质，每次增多的子串个数就是len[New] - len[fa[New]]。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
using namespace std;
typedef long long s64; const int ONE = ;
const int INF = ; int n,x;
s64 Ans; int get()
{
int res=,Q=;char c;
while( (c=getchar())< || c> )
if(c=='-')Q=-;
res=c-;
while( (c=getchar())>= && c<= )
res=res*+c-;
return res*Q;
} struct SAM
{
map <int, int> a[ONE];
int len[ONE], fa[ONE];
int last, cnt;
SAM() {last = cnt = ;}
void Add(int c)
{
int x = last, New = last = ++cnt;
len[New] = len[x] + ;
while(x && !a[x][c]) a[x][c] = New, x = fa[x];
if(!x) {fa[New] = ; Ans += len[New] - len[fa[New]]; return;} int q = a[x][c];
if(len[x] + == len[q]) fa[New] = q;
else
{
int Nq = ++cnt; len[Nq] = len[x] + ;
a[Nq] = a[q];
fa[Nq] = fa[q];
fa[New] = fa[q] = Nq;
while(a[x][c] == q) a[x][c] = Nq, x = fa[x];
}
Ans += len[New] - len[fa[New]];
}
}S; int main()
{
n = get();
while(n--)
{
x = get();
S.Add(x);
printf("%lld\n", Ans);
} }