写了一半 没了啊啊啊 重新写的
思路：
先不考虑后缀自动机 （我不会啊）
那这道题只能用后缀数组了
先把原串倒一下 后缀－＞前缀
相当于每回在前面加了一个字母
求不同的子串个数
首先 正常的求子串个数我们是会的 SPOJ 705
但是这道题比较坑 它让你每回都输出一下
那只好 维护一个前驱 一个后继 求LCP 取max
ans=ans+n-i+1-max(LCP(),LCP())
用set维护前驱和后继就好啦~
//By SiriusRen
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100050;
int n,s[N],sa[N],tsa[N],cntA[N],cntB[N],A[N],B[N],rk[N],ht[N],f[N][20],Log[N];
set<int>SET;long long ans;
void SA(){
for(int i=1;i<=n;i++)cntA[s[i]]++;
for(int i=1;i<=n;i++)cntA[i]+=cntA[i-1];
for(int i=n;i;i--)sa[cntA[s[i]]--]=i;
rk[sa[1]]=1;
for(int i=2;i<=n;i++)rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
for(int l=1;rk[sa[n]]<n;l<<=1){
memset(cntA,0,sizeof(cntA));
memset(cntB,0,sizeof(cntB));
for(int i=1;i<=n;i++)
cntA[A[i]=rk[i]]++,
cntB[B[i]=(i+l<=n?rk[i+l]:0)]++;
for(int i=1;i<=n;i++)cntA[i]+=cntA[i-1],cntB[i]+=cntB[i-1];
for(int i=n;i;i--)tsa[cntB[B[i]]--]=i;
for(int i=n;i;i--)sa[cntA[A[tsa[i]]]--]=tsa[i];
rk[sa[1]]=1;
for(int i=2;i<=n;i++)rk[sa[i]]=rk[sa[i-1]]+(A[sa[i]]!=A[sa[i-1]]||B[sa[i]]!=B[sa[i-1]]);
}
for(int i=1,j=0;i<=n;i++){
j=j?j-1:0;
while(s[i+j]==s[sa[rk[i]-1]+j])j++;
f[rk[i]][0]=j;
}
for(int j=1;j<=19;j++)
for(int i=1;i+(1<<(j-1))<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int LCP(int x,int y){
int t=Log[y-x+1];
return min(f[x][t],f[y-(1<<t)+1][t]);
}
int main(){
scanf("%d",&n),Log[0]=-1;
for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
for(int i=1;i<=n;i++)scanf("%d",&s[i]),sa[i]=s[i];
sort(sa+1,sa+1+n);int u=unique(sa+1,sa+1+n)-sa-1;
for(int i=1;i<=n;i++)s[i]=lower_bound(sa+1,sa+1+u,s[i])-sa;
for(int i=1;i<=n/2;i++)swap(s[i],s[n-i+1]);
SA();
for(int i=n;i;i--){
int jy=0;
set<int>::iterator it=SET.upper_bound(rk[i]);
if(it!=SET.end())jy=LCP(rk[i]+1,*it);
if(it!=SET.begin())jy=max(jy,LCP((*(--it))+1,rk[i]));
ans=ans+n-i+1-jy,SET.insert(rk[i]);
printf("%lld
",ans);
}
}