题解

思路分析

这是一道 后缀数组 + 单调栈 的经典字符串问题。

问题建模

计算所有后缀对之间的差异值之和：

$$\sum_{1 \le i < j \le n} \text{len}(T_i) + \text{len}(T_j) - 2 \cdot \text{lcp}(T_i, T_j) $$

其中 $\text{lcp}(T_i, T_j)$ 是两个后缀的最长公共前缀。

核心思路

1. 展开求和式

$$\sum_{i<j} [\text{len}(T_i) + \text{len}(T_j) - 2\text{lcp}(T_i, T_j)] $$$$= \sum_{i<j} [\text{len}(T_i) + \text{len}(T_j)] - 2\sum_{i<j} \text{lcp}(T_i, T_j) $$

第一部分容易计算：

$$\sum_{i<j} [\text{len}(T_i) + \text{len}(T_j)] = \sum_{i=1}^{n} (n-i) \cdot (n-i+1) $$

关键是计算第二部分。

2. 后缀数组 + height 数组

构建后缀数组 $sa$ 和 height 数组：

• $sa[i]$：排名第 $i$ 的后缀的起始位置
• $height[i] = \text{lcp}(sa[i-1], sa[i])$：相邻后缀的 LCP

3. 单调栈优化

关键观察：对于每个 $height[i]$，它对答案的贡献是多少？

使用单调栈维护：

• 栈中存储 height 值递增的位置
• 对于位置 $i$，它的 height 值会被多少对后缀对用到

具体地，$height[i]$ 对答案的贡献为：

$$\text{贡献} = height[i] \times (\text{左侧比它大的数量}) \times (\text{右侧比它大的数量}) $$

使用单调栈可以高效计算这个贡献。

算法步骤

1. 构建后缀数组：

   • 使用倍增算法构建 $sa$ 数组
   • 计算 $height$ 数组

2. 计算第一部分：

   • $\sum_{i=1}^{n} (n-i)(n-i+1)$

3. 单调栈计算LCP贡献：

   • 遍历 $height$ 数组
   • 使用单调栈维护递增序列
   • 累加每个 $height[i]$ 的贡献

4. 输出答案

复杂度分析

• 后缀数组：$O(n \log n)$
• 单调栈：$O(n)$
• 总时间复杂度：$O(n \log n)$
• 空间复杂度：$O(n)$

#include <bits/stdc++.h>
#define rep(i,s,t) for(int i=(s); i<(t); ++i)
#define forn(i,s,t) for(int i=(s); i<=(t); ++i)
#define form(i,s,t) for(int i=(s); i>=(t); --i)
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int N = 1e6 + 4, M = 500 + 5;
const int Mod = 998244353;
struct mint {
	int r;
	mint() {}
	mint(int _r) : r(_r) {}
	inline friend mint operator + (const mint& A, const mint& B) {
		return mint((A.r + B.r >= Mod) ? (A.r + B.r - Mod) : (A.r + B.r));
	}
	inline friend mint operator - (const mint& A, const mint& B) { return A + mint(Mod - B.r); }
	inline friend mint operator * (const mint& A, const mint& B) { return mint(1ll * A.r * B.r % Mod); }
	inline friend mint& operator += (mint& A, const mint& B) { return A = A + B; }
	inline friend mint& operator -= (mint& A, const mint& B) { return A = A - B; }
	inline friend mint& operator *= (mint& A, const mint& B) { return A = A * B; }
	inline friend mint q_pow(mint p, int k = Mod - 2) {
		mint r = 1;
		for (; k; k >>= 1, p *= p) (k & 1) && (r *= p, 0);
		return r;
	}
};
int n, sa[N], rk[N], trk[N], ton[N], tsa[N]; string s;
inline void dsort() {
	int m = 127;
	forn (i, 1, n) ton[rk[i] = s[i]] ++ ;
	forn (i, 2, m) ton[i] += ton[i - 1];
	form (i, n, 1) sa[ton[rk[i]] -- ] = i;
	for (int w = 1, p = 0; ; w <<= 1, m = p, p = 0) {
		forn (i, n - w + 1, n) tsa[++p] = i;
		forn (i, 1, n) if (sa[i] > w) tsa[++p] = sa[i] - w;
		memset(ton, 0, m + 1 << 2);
		memcpy(trk, rk, n + 1 << 2);
		p = 0;
		forn (i, 1, n) ton[rk[i]] ++ ;
		forn (i, 2, m) ton[i] += ton[i - 1];
		form (i, n, 1) sa[ton[rk[tsa[i]]]--] = tsa[i];
		forn (i, 1, n) 
			if (trk[sa[i - 1]] == trk[sa[i]] && trk[sa[i - 1] + w] == trk[sa[i] + w])
				rk[sa[i]] = p;
			else 
				rk[sa[i]] = ++p;
		if (p == n) break ;
	}
}
int ht[N];
inline void geth() {
	for (int i = 1, k = 0; i <= n; ++i) {
		k && (k --, 0);
		while (s[i + k] == s[sa[rk[i] - 1] + k])
			++k;
		ht[rk[i]] = k;
	}
}
int stk[N], top; ll sum[N];
inline void solve() {
	cin >> s;
	n = s.size();
	s = "$" + s + "$";
	dsort(), geth();
	ll ans = 1ll * (n - 1) * n * (n + 1) / 2;
//	forn (i, 1, n) cout << sa[i] << " \n"[i == n];
//	forn (i, 1, n) cout << ht[i] << " \n"[i == n];
	forn (i, 1, n) {
		while (top && ht[i] <= ht[stk[top]])
			top -- ;
		stk[++top] = i;
		sum[top] = sum[top - 1] + 1ll * (i - stk[top - 1]) * ht[i];
		ans -= 2ll * sum[top];
	}
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int z;
	z = 1;
//	cin >> z;
	while (z -- ) solve(); 
	return 0;
}
/*
*/

题解

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

$$\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;
}