写了一半 没了啊啊啊 　　　　重新写的

思路：

先不考虑后缀自动机　　　（我不会啊）

那这道题只能用后缀数组了

先把原串倒一下　　后缀－＞前缀

相当于每回在前面加了一个字母

求不同的子串个数　

首先　正常的求子串个数我们是会的　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\n",ans);

    }

}