题解

两两后缀之间的差异可以写成

$$\sum_{i<j} \bigl(|T_i|+|T_j| - 2\operatorname{lcp}(T_i,T_j)\bigr), $$

即所有后缀长度之和减去所有公共前缀长度贡献。前一部分可以直接算出，关键在于如何快速统计后一部分。

先用倍增 + 基数排序构建后缀数组和高度数组 height，其中 height[k] 表示 sa[k] 与 sa[k-1] 的最长公共前缀。对于固定的 height[k] = h，它会作为一段连续后缀对的最小值出现：设它左侧可以扩展到的位置为 L，右侧可以扩展到的位置为 R，那它一共会贡献 $(k-L+1) * (R-k+1)$ 个后缀对，每对的 lcp 至少为 $h$。因此只要维护每个 height 在数组中的“下一个更小值/严格更小值”位置即可。

具体实现时，利用单调栈分别求出 sl[k]（左侧第一个严格小于 height[k] 的下标）和 sr[k]（右侧第一个小于等于 height[k] 的下标），于是 height[k] 的贡献次数就是 $(k-sl[k]+1)*(sr[k]-k+1)$。把这些贡献乘以 2 从总和中扣掉，就得到最终答案。整体复杂度为 $O(n)$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5;
string str; int n;

int sa[N + 10], pos[N + 10], tab[N + 10], rnk[N + 10], height[N + 10];
int sl[N + 10], sr[N + 10], sta[N + 10], top = 0;
namespace SA {
	int m;
	void radix() {
		for(int i = 0; i <= m; i++) tab[i] = 0;
		for(int i = 1; i <= n; i++) tab[rnk[i]]++;
		for(int i = 1; i <= m; i++) tab[i] += tab[i - 1];
		for(int i = n; i >= 1; i--) sa[tab[rnk[pos[i]]]--] = pos[i];
	}
	void solve() {
		m = 26;
		for(int i = 1; i <= n; i++)
			pos[i] = i, rnk[i] = str[i] - 'a' + 1;
		radix();
		for(int w = 1, cnt = 0; cnt < n; w <<= 1, m = cnt) {
			cnt = 0;
			for(int i = 1; i <= w; i++) pos[++cnt] = n - i + 1;
			for(int i = 1; i <= n; i++) if(sa[i] > w) pos[++cnt] = sa[i] - w;
			radix(); swap(rnk, tab);
			cnt = rnk[sa[1]] = 1;
			for(int i = 2; i <= n; i++)
				rnk[sa[i]] = ((tab[sa[i]] == tab[sa[i - 1]] && tab[sa[i] + w] == tab[sa[i - 1] + w]) ? (cnt) : (++cnt));
		}
		
		for(int i = 1, k = 0; i <= n; i++) {
			if(rnk[i] == 1) {
				height[1] = 0;
				continue;
			}
			if(k) k--;
			while(str[i + k] == str[sa[rnk[i] - 1] + k]) k++;
			
			height[rnk[i]] = k;
		}
		
		for(int i = 1; i <= n; i++) {
			while(top)
				if(height[sta[top]] > height[i]) top--;
				else break;
			sl[i] = sta[top] + 1;
			sta[++top] = i;
		}
		top = 0, sta[0] = n + 1;
		for(int i = n; i >= 1; i--) {
			while(top) 
				if(height[sta[top]] >= height[i]) top--;
				else break;
			sr[i] = sta[top] - 1;
			sta[++top] = i;
		}
//		for(int i = 1; i <= n; i++)
//			cout << height[i] << ' ' << sl[i] << ' ' << sr[i] << endl;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> str; str = "#" + str, n = str.size() - 1;
	SA::solve();
	ll sum = 0;
	for(int i = 1; i <= n; i++) {
		sum += 1ll * (n - i + 1) * (n - i);
		sum += 1ll * (n - i + 1) * 1ll * (n - i) / 2ll; 
	}
	
	for(int i = 1; i <= n; i++)
		sum -= 2ll * (i - sl[i] + 1) * (sr[i] - i + 1) * 1ll * height[i];
	cout << sum << endl;
}