bzoj[3238][ahoi差异]

Description

Input

一行，一个字符串S

Output

一行，一个整数，表示所求值

Sample Input

cacao

Sample Output

HINT

2<=N<=500000,S由小写英文字母组成

Solution

首先，对于原式中的len(Ti)+len(Tj)可以简单初始化得到，即1*(n-1)+…+i*(n-1)+…+n*(n-1)

此题的难点在于怎样求解2*LCP(Ti,Tj)的值

利用后缀数组的性质，可以看出，求LCP(Ti,Tj)即求min{h[rank[i]],…,h[rank[j]]}

对于此题，由于不用修改，我们不用考虑两两枚举i、j串再求最小值，只要考虑对于每个后缀i对其前后区间的最小值的贡献

设对于i点，它的最小值贡献区间为l[i],r[i]

则i对原始的贡献为 -(i-l[i]+1)*(r[i]-i+1)*h[i]

那么，就可以很容易的求解此题了