SDOI 2016 生成魔咒

题目大意：一个字符串，刚开始为空，依次在后面添加一个字符，问每次添加完字符后本质不同的字符串有多少种

后缀自动机裸题，添加字符时，更新的结点个数即为新增加的子串

#include<bits/stdc++.h>

using namespace std;

inline int read(){

    int s=;char ch=getchar();

    for(;ch<''||ch>'';ch=getchar());

    for(;ch>=''&&ch<='';ch=getchar())s=s*+ch-'';

    return s;

}

struct sam{

    int cnt,last;

    int fa[],l[];

    map<int,int>a[];

    long long ans;

    sam(){

        last=++cnt;

    }

    void add(int c){

        int p=last,np=last=++cnt;l[np]=l[p]+;

        while(p&&!a[p][c])a[p][c]=np,p=fa[p];

        if(!p)fa[np]=;

        else{

            int q=a[p][c];

            if(l[q]==l[p]+)fa[np]=q;

            else{

                int nq=++cnt;l[nq]=l[p]+;

                a[nq]=a[q];

                fa[nq]=fa[q];

                fa[np]=fa[q]=nq;

                while(a[p][c]==q)a[p][c]=nq,p=fa[p];

            }

        }

        ans+=l[last]-l[fa[last]];

        printf("%lld\n",ans);

    }

}sam;

int main(){

    freopen("menci_incantation.in","r",stdin);

    freopen("menci_incantation.out","w",stdout);

    int n=read();

    for(int i=;i<=n;++i){

        int x=read();sam.add(x);

    }return ;

}