神仙题。或者可能我太菜了没见过后缀数组的骚操作，然后就被秀了一脸(hhhhh)
$$sumlimits_{1<=i < j <= n} len(T_i) + len(T_j) - 2 * lcp (T_i, T_j)$$
这个式子我们显然可以把前面拆出来当常数算（({(n - 1) * n * (n + 1) }/ 2)），剩下的就是怎么计算每个区间的(lcp)之和了。
这个问题，我们转化成后缀数组的(height)来进行计算。仔细思考会发现，原字符串的每对(i)和(j)事实上和(height)数组的每一段区间([rk[i], rk[j]])一一对应。至此，我们的问题又转化成了求(height)数组上的每一个区间的最小值之和。
暴力求显然是(O(N^2))的，承受不住。根据(lcp)具有可合并性$ min(lcp (T_i,T_ j), lcp (T_{j + 1}, T_{k})) = lcp (T_i, T_k)(，而)height(数组又代表了)lcp(T_i, T_{sa[rk[i ] - 1]})$，那么我们就可以这么做：
-
设(dp[i])为(height)数组中前缀(i)的每一个后缀贡献出的答案。
-
对于任意(i > p)，当(height[i] >= height[p])时，我们可以在所有(height[p])统治的答案里，在后面缀上一个([p-1,i])的区间，所以可以认为是：前缀(i)的贡献中，还要包含一个前缀(p)的总贡献。
-
所以只要计算最近的一个(p)就可以囊括([1,p])内的所有答案，维护最近的小于(height[i])的(p)的位置即可。
-
所以有(f[i] = f[p] + (i - p) * height[i];)
-
如果(i)的前面不存在(p)，满足(height[p] <= height[i])，那么前缀([1,i])的所有后缀(height)的最小值都是(height[i])（被(i)统治），即贡献为(i * height[i])。
为了维护前一个比(height[i])小的(height)值的相关信息，我们需要开一个递增的单调栈，遍历到(i)时弹出所有(height)值小于(height[i])的元素，结束时再插入该(height)。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 500010;
char s[N];
int n, m = 255, sa[N], tp[N];
int rk[N], _rk[N], bin[N], height[N];
void base_sort () {
for (int i = 0; i <= m; ++i) bin[i] = 0;
for (int i = 1; i <= n; ++i) bin[rk[tp[i]]]++;
for (int i = 1; i <= m; ++i) bin[i] += bin[i - 1];
for (int i = n; i >= 1; --i) sa[bin[rk[tp[i]]]--] = tp[i];
}
void suffix_sort () {
for (int i = 1; i <= n; ++i) {
tp[i] = i;
rk[i] = s[i - 1];
}
base_sort ();
for (int w = 1; w <= n; w <<= 1) {
int cnt = 0;
for (int i = n - w + 1; i <= n; ++i) {
tp[++cnt] = i;
}
for (int i = 1; i <= n; ++i) {
if (sa[i] > w) {
tp[++cnt] = sa[i] - w;
}
}
base_sort ();
memcpy (_rk, rk, sizeof (rk));
rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; ++i) {
rk[sa[i]] = _rk[sa[i]] == _rk[sa[i - 1]] && _rk[sa[i] + w] == _rk[sa[i - 1] + w] ? cnt : ++cnt;
}
if (cnt == n) break;
m = cnt;
}
// printf ("sa : ");for (int i = 1; i <= n; ++i) printf ("%d ", sa[i]); printf ("
");
}
void get_height () {
int k = 0;
for (int i = 1; i <= n; ++i) {
if (k) k--;
int j = sa[rk[i] - 1];
while (s[i + k - 1] == s[j + k - 1]) ++k;
height[rk[i]] = k;
}
// printf ("height : ");
// for (int i = 1; i <= n; ++i) {
// printf ("%d ", height[i]);
// }
// printf ("
");
}
struct node {
int pos, val;
node (int ppos = 0, int vval = 0) {pos = ppos, val = vval;}
};
node sta[N]; int top;
LL f[N];
int main () {
scanf ("%s", s);
n = strlen (s);
suffix_sort ();
get_height ();
for (int i = 1; i <= n; ++i) {
while (top > 0 && sta[top].val > height[i]) --top;
//使sta[top].val <= height[i];
if (top > 0) {
int p = sta[top].pos; //p记录控制范围
f[i] = f[p] + (i - p) * height[i];
} else {
f[i] = i * height[i];
}
sta[++top] = node (i, height[i]);
}
LL ans = 1LL * (n - 1) * n * (n + 1) / 2;
for (int i = 1; i <= n; ++i) {
ans -= 2 * f[i];
}
cout << ans << endl;
}