4516: [Sdoi2016]生成魔咒

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?1460??Solved:?835
[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 次操作加入的魔咒字符。 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

HINT

Source

鳴謝Menci上傳

后綴自動機裸題，，，， /**************************************************************Problem: 4516User: JYYHHLanguage: C++Result: AcceptedTime:792 msMemory:14936 kb ****************************************************************/#include<bits/stdc++.h> #define ll long long #define maxn 200005 using namespace std; map<int,int> ch[maxn]; int n,m,cnt=1,pre=1,k; int l[maxn],f[maxn]; ll ans=0;inline void ins(int x){int p=pre,np=++cnt;pre=np,l[np]=l[p]+1;for(;p&&!ch[p].count(x);p=f[p]) ch[p][x]=np;if(!p) f[np]=1;else{int q=ch[p][x];if(l[q]==l[p]+1) f[np]=q;else{int nq=++cnt;l[nq]=l[p]+1;ch[nq]=ch[q];ans-=(ll)l[q]-l[f[q]];f[nq]=f[q];f[q]=f[np]=nq;ans+=(ll)l[q]-l[f[q]];ans+=(ll)l[nq]-l[f[nq]];for(;ch[p][x]==q;p=f[p]) ch[p][x]=nq;}}ans+=(ll)l[np]-l[f[np]]; }int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&k);ins(k);printf("%lld\n",ans);}return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/8504947.html

總結

以上是生活随笔為你收集整理的[SDOI2016]生成魔咒的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。