【BZOJ4516】【SDOI2016】生成魔咒 [SAM]

生成魔咒

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

Sample Output

　　1
　　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);

         }

 }

巴特西