自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 21:58:09，当前版本为作者最后更新于2018-12-15 17:53:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意简述：

定义两个字符串 $S$ 和 $T$ 的差异 $\operatorname{diff}(S,T)$ 为这两个串的长度之和减去两倍的这两个串的最长公共前缀的长度。

给定一个字符串，定义从第 $i$ 个字符开始的后缀为 $Suf_i$。

求 $\sum_{1\le i<j\le n}\operatorname{diff}(Suf_i,Suf_j)$。

题解：

化简式子，原式等于

$$\begin{aligned}&\left(\sum_{1\le i<j\le n}i+j\right)-2\times\sum_{1\le i<j\le n}\operatorname{lcp}(Suf_i,Suf_j)\\=&\frac{n(n-1)(n+1)}{2}-2\times\sum_{1\le i<j\le n}\operatorname{lcp}(Suf_i,Suf_j)\end{aligned} $$

所以只要求出后半部分即可。

建立字符串的后缀数组。

考虑 Height 数组的贡献：Height 数组中 [2, n] 内的每一个区间都给答案贡献区间最小值。

套路：每个区间的区间最小值之和，使用单调栈解决。

#include <cstdio>
#include <cstring>

typedef long long LL;
const int MN = 500005;

int N;
char str[MN];

int M;
int rk[MN], rk2[MN], SA[MN], SA2[MN];
int buk[MN], cnt;
int Height[MN];

void GetHeight() {
	int k = 0;
	for (int i = 1; i <= N; ++i) {
		if (rk[i] == 1) { k = Height[1] = 0; continue; }
		if (k) --k;
		int j = SA[rk[i] - 1];
		while (i + k <= N && j + k <= N && str[i + k] == str[j + k]) ++k;
		Height[rk[i]] = k;
	}
}

void Rsort() {
	for (int i = 1; i <= M; ++i) buk[i] = 0;
	for (int i = 1; i <= N; ++i) ++buk[rk[i]];
	for (int i = 1; i <= M; ++i) buk[i] += buk[i - 1];
	for (int i = N; i >= 1; --i) SA[buk[rk[SA2[i]]]--] = SA2[i];
}

void GetSA() {
	M = 26;
	for (int i = 1; i <= N; ++i) rk[i] = str[i] - 'a' + 1, SA2[i] = i;
	Rsort();
	for (int j = 1; j < N; j <<= 1) {
		int P = 0;
		for (int i = N - j + 1; i <= N; ++i) SA2[++P] = i;
		for (int i = 1; i <= N; ++i) if (SA[i] > j) SA2[++P] = SA[i] - j;
		Rsort();
		rk2[SA[1]] = P = 1;
		for (int i = 2; i <= N; ++i) {
			if (rk[SA[i]] != rk[SA[i - 1]] || rk[SA[i] + j] != rk[SA[i - 1] + j]) ++P;
			rk2[SA[i]] = P;
		}
		for (int i = 1; i <= N; ++i) rk[i] = rk2[i];
		M = P;
		if (M == N) break;
	}
	GetHeight();
}

int st[MN], t;
int L[MN], R[MN];

int main() {
	scanf("%s", str + 1);
	N = strlen(str + 1);
	GetSA();
	st[t = 1] = 1;
	for (int i = 2; i <= N; ++i) {
		while (t && Height[st[t]] > Height[i]) R[st[t--]] = i;
		L[i] = st[t];
		st[++t] = i;
	} while (t) R[st[t--]] = N + 1;
	LL Ans = (LL)(N - 1) * N * (N + 1) / 2;
	for (int i = 2; i <= N; ++i)
		Ans -= 2ll * (R[i] - i) * (i - L[i]) * Height[i];
	printf("%lld\n", Ans);
	return 0;
}