【SDOI2016】bzoj4516 生成魔咒【解法一】

每次在SAM中加入一個字元，維護每個點的 vali−valfaili 即可。

因為字元集很大，離散化以後也開不下，可以用map存轉移。

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=;
map<int,int> trans[maxn];
int fail[maxn],val[maxn],n,tot=;
void check()
{
    for (int i=;i<=tot;i++)
        for (map<int,int>::iterator it=trans[i].begin();it!=trans[i].end();++it)
            printf("%d-%d->%d\n",i,(*it).first,(*it).second);
}
int main()
{
    LL ans=;
    int last=,p,np,q,nq,x;
    scanf("%d",&n);
    for (int i=;i<=n;i++)
    {
        scanf("%d",&x);
        p=last;
        val[last=np=++tot]=val[p]+;
        while (p&&!trans[p].count(x))
        {
            trans[p][x]=np;
            p=fail[p];
        }
        if (!p) fail[np]=,ans+=val[np];
        else
        {
            q=trans[p][x];
            if (val[q]==val[p]+) fail[np]=q,ans+=val[np]-val[q];
            else
            {
                val[nq=++tot]=val[p]+;
                fail[nq]=fail[q];
                fail[np]=fail[q]=nq;
                trans[nq]=trans[q];
                while (p&&trans[p][x]==q)
                {
                    trans[p][x]=nq;
                    p=fail[p];
                }
                ans+=val[np]-val[nq];
            }
        }
        //if (i==5) check();
        printf("%lld\n",ans);
    }
}