后缀数组笔记。

这题是紫的？估计难度全在模板了吧。

$$\displaystyle \sum_{1\leqslant i<j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$

$$=\frac{n(n-1)(n+1)}{2} - 2 \times \displaystyle \sum_{1\leqslant i<j\leqslant n} \operatorname{lcp}(T_i,T_j)$$

后面相当于 height 数组的区间最小值之和。

做完了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n;
char s[N];

int sa[N], rk[N], x[N], y[N];
int cnt[N];
void init_SA() {
    int v = 128;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) ++cnt[x[i] = s[i]];
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;

    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > len) y[++tot] = sa[i] - len;

        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) ++cnt[x[i]];
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;
        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        }
        v = tot;
        if (v == n) break;
    }
}

int ht[N];
void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1];
        if (now) now--;
        while (i + now <= n && j + now <= n && s[i + now] == s[j + now]) now++;
        ht[rk[i]] = now;
    }
}

long long ans = 0, sum = 0;
int stk[N], top = 0;
int l[N], r[N];
void solve() {
    ans = n * 1ll * (n - 1) / 2 * 1ll * (n + 1);
    for (int i = 2; i <= n; i++) {
        while (top && ht[i] <= ht[stk[top]]) r[stk[top]] = i, top--;    //注意取等和不取等条件
        stk[++top] = i;
    }
    while (top) r[stk[top--]] = n + 1;
    for (int i = n; i >= 2; i--) {
        while (top && ht[i] < ht[stk[top]]) l[stk[top]] = i, top--;
        stk[++top] = i;
    }
    while (top) l[stk[top--]] = 1;
    for (int i = 2; i <= n; i++) sum += ht[i] * 1ll * (r[i] - i) * 1ll * (i - l[i]);
    printf("%lld\n", ans - 2 * sum);
}

int main() {
    scanf("%s", s + 1), n = strlen(s + 1);
    init_SA(), init_height();
    solve();
    return 0;
}