【刷题】BZOJ 4516 [Sdoi2016]生成魔咒

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 次操作加入的魔咒字符。

1≤n≤100000。,用来表示魔咒字符的数字 x 满足 1≤x≤10^9

Output

输出 n 行，每行一个数。第 i 行的数表示第 i 次操作后 S 的生成魔咒数量

Sample Input

7  
1 2 3 3 3 1 2

Sample Output

1  
3  
6  
9  
12  
17  
22

Solution

SAM模板题

每次加入新字符，对答案造成的贡献是 (len[x]-len[fa[x]]) ，因为以新字符为结尾，开头可以有 (len[x]-len[fa[x]]) 种情况

然后字符集的范围是真的无聊，于是就上了pbds的hash_table

#include
#include
#include
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
using namespace __gnu_pbds;
const int MAXN=100000+10;
int las=1,tot=1,len[MAXN<<1],fa[MAXN<<1],n;
ll ans;
cc_hash_table ch[MAXN<<1];
template inline void read(T &x)
{T data=0,w=1;char ch=0;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();x=data*w;
}
template inline void write(T x,char ch='')
{if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');if(ch!='')putchar(ch);
}
template inline void chkmin(T &x,T y){x=(y inline void chkmax(T &x,T y){x=(y>x?y:x);}
template inline T min(T x,T y){return x inline T max(T x,T y){return x>y?x:y;}
inline ll extend(int c)
{int p=las,np=++tot;las=np;len[np]=len[p]+1;while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];if(!p)fa[np]=1;else{int q=ch[p][c];if(len[q]==len[p]+1)fa[np]=q;else{int nq=++tot;fa[nq]=fa[q];ch[nq]=ch[q];len[nq]=len[p]+1,fa[q]=fa[np]=nq;while(p&&ch[p][c]==q)ch[p][c]=nq,p=fa[p];}}return len[np]-len[fa[np]];
}
int main()
{read(n);for(register int i=1,x;i<=n;++i){read(x);ans+=extend(x);write(ans,'
');}return 0;
}