# bzoj 3238 差异

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long ans;
char st[510000];
int sum[510000],c[510000],h[510000],sa[2][510000],rk[2][510000];
int n,p,q,k,num;
void mul(int *sa,int *rk,int *sa1,int *rk1)
{
for (int i=1;i<=n;i++) sum[rk[sa[i]]]=i;
for (int i=n;i;i--)
if (sa[i]>k) sa1[sum[rk[sa[i]-k]]--]=sa[i]-k;
for (int i=n-k+1;i<=n;i++) sa1[sum[rk[i]]--]=i;
for (int i=1;i<=n;i++)
rk1[sa1[i]]=rk1[sa1[i-1]]+(rk[sa1[i-1]]!=rk[sa1[i]]||rk[sa1[i-1]+k]!=rk[sa1[i]+k]);
}
int main()
{
scanf("%s",st+1);
n=strlen(st+1);
for (int i=1;i<=n;i++) sum[st[i]-'a']++;
for (int i=1;i<26;i++) sum[i]+=sum[i-1];
p=0,q=1;
for (int i=1;i<=n;i++) sa[p][sum[st[i]-'a']--]=i;
for (int i=1;i<=n;i++) rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(st[sa[p][i-1]]!=st[sa[p][i]]);
for (k=1;k<n;k<<=1,swap(p,q)) mul(sa[p],rk[p],sa[q],rk[q]);
for (int k=0,i=1;i<=n;i++)
{
int j=sa[p][rk[p][i]-1];
while (st[i+k]==st[j+k]) k++;
h[rk[p][i]]=k; if (k>0) k--;
}
for (int i=1;i<=n;i++) ans=1ll*(n-1)*(n+1)*n/2;
long long sums=0;
int num=0;
for (int i=1;i<=n;i++)
{
while (num>0&&h[c[num]]>=h[i]) sums-=1ll*(c[num]-c[num-1])*h[c[num]],num--;
c[++num]=i;
sums+=1ll*(c[num]-c[num-1])*h[c[num]];
ans-=2*sums;
}
printf("%lld\n",ans);
}

### 2 thoughts on “bzoj 3238 差异”

1. My spouse and i ended up being quite happy that Albert could round up his studies through the entire ideas he made using your web page. It is now and again perplexing just to find yourself offering instructions that people today have been making money from. And we also fully understand we now have the website owner to be grateful to for this. The specific explanations you’ve made, the straightforward site navigation, the relationships you will give support to foster – it is mostly great, and it is letting our son and our family reckon that the subject is entertaining, and that’s very important. Thanks for the whole thing!

2. I want to express some appreciation to you for bailing me out of this particular instance. Just after searching throughout the the web and seeing recommendations that were not pleasant, I assumed my entire life was done. Living without the presence of approaches to the problems you’ve sorted out through your posting is a critical case, and the kind which could have in a wrong way affected my entire career if I hadn’t noticed your web page. The skills and kindness in touching almost everything was precious. I don’t know what I would have done if I hadn’t encountered such a thing like this. I can also at this point look forward to my future. Thanks for your time very much for this high quality and results-oriented guide. I will not think twice to endorse your blog post to any person who wants and needs guidance on this subject.