搞了一上午+接近一下午这个题，然后被屠了个稀烂，默默仰慕一晚上学会SAM的以及半天4道SAM的hxy大爷。
题目链接：http://hihocoder.com/problemset/problem/1413
这个题非常的劲！
首先可以发现，每次只变换一个字符为#，所以每次答案一定会得到相应的包含#的答案，而这个方案是可以直接计算出来的。
假设是$S[i]=$#则会得到$i*(N-i+1)$的子串数。
所以每次的答案可以表示为$sum[root]+i*(N-i+1)-ans[i]$，其中$ans[i]$表示严格经过$i$位置的本质不同的子串，严格的意义即这个本质不同的子串有且仅有一次，且经过$i$；
所以问题就转化为如何求出$ans[1..N]$
然后如何找到本质不同的经过$i$的子串，考虑利用后缀自动机；
问了 abclzr队长 ，可以考虑存出每个$Parent$树中的节点的$Right$集合，这样再进行递推，就可以搞出答案，但实际上并不需要存出全部的$Right$集合，只需要记录每个节点的$Right$集合的最左最右端点。
这样，对于一个子串是否严格跨越$i$，就可以利用右端-距离+1以及左端来判断是否严格跨越。
然后每个节点代表了多个子串，把这些子串一起处理，对答案的贡献就相当于是区间加上一个等差数列，对$ans[]$二阶差分后可以$O(N)$出解。
其实也可以用线段树/树状数组维护，树状数组需要差分，而且构造两个比较好写，线段树只要支持区间加，单点加，区间和即可。
给出一下官方题解：
Code：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define LL long long
#define MAXN 600010
int N;
char S[MAXN];
namespace SAM
{
int son[MAXN<<][],par[MAXN<<],len[MAXN<<],size[MAXN<<],l[MAXN<<],r[MAXN<<];
int root,last,sz;
#define INF 0x7fffffff
inline void Init() {root=last=sz=;}
inline void Extend(int c)
{
int cur=++sz,p=last;
len[cur]=len[p]+; size[cur]=;
while (p && !son[p][c]) son[p][c]=cur,p=par[p];
if (!p) par[cur]=root;
else
{
int q=son[p][c];
if (len[p]+==len[q]) par[cur]=q;
else
{
int nq=++sz; l[nq]=INF,r[nq]=;
memcpy(son[nq],son[q],sizeof(son[nq]));
par[nq]=par[q]; len[nq]=len[p]+;
while (p && son[p][c]==q) son[p][c]=nq,p=par[p];
par[cur]=par[q]=nq;
}
}
l[cur]=r[cur]=len[cur];
last=cur;
}
inline void Build() {Init(); for (int i=; i<=N; i++) Extend(S[i]-'a'+);}
int st[MAXN],id[MAXN<<];
LL sum[MAXN<<],ans[MAXN];
inline void Pre()
{
for (int i=; i<=sz; i++) st[len[i]]++;
for (int i=; i<=N; i++) st[i]+=st[i-];
for (int i=; i<=sz; i++) id[st[len[i]]--]=i;
for (int i=sz; i>=; i--)
{
int x=id[i];
l[par[x]]=min(l[par[x]],l[x]);
r[par[x]]=max(r[par[x]],r[x]);
for (int j=; j<=; j++)
sum[x]+=sum[son[x][j]];
sum[x]++;
}
sum[root]--;
for (int i=sz; i>=; i--)
{
int x=id[i];
if (r[x]-len[x]+<=l[x])
{
int L=r[x]-len[x]+,R=min(r[x]-len[par[x]],l[x]),Len=R-L+;
if (L<=R) ans[L]++,ans[R+]-=Len+,ans[R+]+=Len;
L=R+,R=l[x];
if (L<=R) ans[L]+=Len,ans[L+]-=Len,ans[R+]-=Len,ans[R+]+=Len;
}
}
for (int i=; i<=N; i++) ans[i]+=ans[i-];
for (int i=; i<=N; i++) ans[i]+=ans[i-];
// printf("%d\n",sum[root]);
}
}using namespace SAM;
int main()
{
scanf("%d%s",&N,S+);
SAM::Build(); SAM::Pre();
for (int i=; i<=N; i++) printf("%lld ",(LL)i*(N-i+)+sum[root]-ans[i]);
return ;
}
/*
10
abcabcabdc
*/
hihocoder challenge 24 C