Luogu

BZOJ

分析

$\mathrm{SAM}$ 。

如果只在最后询问的话，显然答案是 $\sum len[i]-len[fa[i]]$ 。

因为 $\mathrm{SAM}$ 是在线算法，所以可以考虑每次新加进来的节点的贡献：显然是 $len[i]-len[fa[i]]$ 。

于是就做完了。

然后因为 $x\leq 10^9$ ，所以要用一个 $\mathrm{map}$ 或者 $\mathrm{unordered\_map}$ 来记子节点。

代码

//It is made by M_sea
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

unordered_map<int,int> ch[N];
int fa[N],len[N];
int last=1,tot=1;
ll ans=0;

inline void extend(int c) {
    int p=last,np=++tot; last=np,len[np]=len[p]+1;
    for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
    if (!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if (len[p]+1==len[q]) fa[np]=q;
        else {
            int nq=++tot; len[nq]=len[p]+1;
            ch[nq]=ch[q];
            fa[nq]=fa[q],fa[q]=fa[np]=nq;
            for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
    ans+=len[np]-len[fa[np]];
}

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) extend(read()),printf("%lld\n",ans);
    return 0;
}