Time:2016.05.23
Author:xiaoyimi
转载注明出处谢谢

传送门
思路：
题意已经说的很明白了。
关键在于如何快速求得各lcp的和
有一个重要的性质

排名为i和j（i＜j）的最长前缀长度=min(height[i+1..j])

对于排名为i的后缀，想要求得 $f[i]=∑lcp(i,j)$(i＜j)我们只用维护好(i,j]区间的height最小值就好，而且如果遇到某个j，height[j]比height[i]小，那么j及其后的后缀对答案的贡献就是f[j]了，j之前的后缀一共是j-i个，对答案的贡献就是height[i]*(j-i)；反之如果height[j]>=height[i]，那么height[j]以后对答案没有任何贡献（因为有比它小的height[i]存在），直接排除它，也就是说对于height的使用是存在单调性的，使用单调栈就好（一开始我还不怎么会单调栈，蛋疼了好久）
注意：
1.起初对栈底放入len+1，使得栈不为空，从而计算各个值
2.对于原式中lcp以外的东西，我们可以把它化成（n是字符串长度）
$(\frac{n(n+1)(2n+1)}6-\frac{n(n+1)}2)*\frac32$
代码：

#include<bits/stdc++.h>
#define M 500004
#define LL long long 
using namespace std;
char s[M];
int w[M],cnt[M],sa[M],rank[M],tmp[M],id[M],height[M];
LL ans,f[M];
stack<int>S;
void SA(int len,int up)
{int *rk=rank,p=0,*t=tmp,d=1;for (int i=0;i<len;i++) cnt[rk[i]=w[i]]++;for (int i=1;i<up;i++) cnt[i]+=cnt[i-1];for (int i=len-1;i>=0;i--) sa[--cnt[rk[i]]]=i;for (;;){for (int i=len-d;i<len;i++) id[p++]=i;for (int i=0;i<len;i++)if (sa[i]>=d) id[p++]=sa[i]-d;for (int i=0;i<up;i++) cnt[i]=0;for (int i=0;i<len;i++) cnt[t[i]=rk[id[i]]]++;for (int i=1;i<up;i++) cnt[i]+=cnt[i-1];for (int i=len-1;i>=0;i--) sa[--cnt[t[i]]]=id[i];swap(t,rk);p=1;rk[sa[0]]=0;for (int i=0;i<len-1;i++)if (sa[i]+d<len&&sa[i+1]+d<len&&t[sa[i]]==t[sa[i+1]]&&t[sa[i]+d]==t[sa[i+1]+d])rk[sa[i+1]]=p-1;elserk[sa[i+1]]=p++;if (p==len) break;d<<=1;up=p;p=0;}
}
void Height(int len)
{for (int i=1;i<=len;i++) rank[sa[i]]=i;int k=0,x;for (int i=0;i<len;i++){k=max(k-1,0);x=sa[rank[i]-1];while (w[i+k]==w[x+k]) k++;height[rank[i]]=k;}
} 
main()
{scanf("%s",s);int len=strlen(s);ans=((LL)len*(len+1)*(len*2+1)/6-(LL)len*(len+1)/2)*3/2;for (int i=0;i<len;i++) w[i]=s[i]-'a'+1;SA(len+1,28);Height(len);S.push(len+1);for (int i=len;i>=1;i--){while(height[S.top()]>height[i]) S.pop();f[i]=(LL)height[i]*(S.top()-i)+f[S.top()];ans-=f[i]<<1;S.push(i);}printf("%lld",ans);
}