LibreOJ 2033 「SDOI2016」生成魔咒

由于后缀自动机的构造本来就是一个在线的过程，所以我们可以考虑每次往答案中添加新的贡献。

又根据后缀自动机的定义，不同子串的个数其实就是 tot∑i=1leni−lenfai。
所以我们再每次添加字符的时候更新答案即可。

这题如果用 SA 来做的话会很麻烦，但是 SAM 就很简洁了。

代码：

#include <cstdio>
#include <tr1/unordered_map>
using namespace std;
using namespace tr1;
const int N = 1e5;
int n;
int a[N + 5];
unordered_map<int,int> hs;
int cnt;
struct node
{
    unordered_map<int,int> ch;
    int fa,len;
} sam[(N << 1) + 5];
long long ans;
int whole = 1,tot = 1;
void push(int x)
{
    int cur = whole,p = whole = ++tot;
    sam[p].len = sam[cur].len + 1;
    for(;cur && !sam[cur].ch.count(x);cur = sam[cur].fa)
        sam[cur].ch[x] = p;
    if(!cur)
        sam[p].fa = 1;
    else
    {
        int q = sam[cur].ch[x];
        if(sam[cur].len + 1 == sam[q].len)
            sam[p].fa = q;
        else
        {
            int nxt = ++tot;
            sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
            for(;cur && sam[cur].ch.count(x) && sam[cur].ch[x] == q;cur = sam[cur].fa)
                sam[cur].ch[x] = nxt;
        }
    }
    ans += sam[p].len - sam[sam[p].fa].len;
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),a[i] = hs.count(a[i]) ? hs[a[i]] : (hs[a[i]] = ++cnt),push(a[i]),printf("%lld\n",ans);
}