[BZOJ 3238][AHOI 2013] 差异

题目大意

长度为 \(n\) 的字符串 \(S\),记 \(T_i\) 为其从第 \(i\) 个字符开始的后缀,求: \[ \sum_{1 \leqslant i < j \leqslant n} len(T_i) + len(T_j) - 2 \; lcp(T_i, \; T_j) \] \(1 \leqslant n \leqslant 500,000\)

题目链接

BZOJ 3238

题解

将所求式分成两部分。

第一部分易得为: \[ \sum_{1 \leqslant i < j \leqslant n} len(T_i) + len(T_j) = (n - 1) \times \frac{n (n + 1)}2 \] 因为每个后缀均被枚举了 \(n - 1\) 次。

第二部分(不管系数),由后缀数组中 \(height\) 数组的性质可化为: \[ \begin{align} \sum_{1 \leqslant i < j \leqslant n} lcp(T_i, \; T_j) &= \sum_{1 \leqslant i < j \leqslant n} min(height[k]), \; k \in [rank[i] + 1, \; rank[j]] \\ &= \sum_{1 \leqslant i < j \leqslant n} min(height[k]), \; k \in [i + 1, \; j] \end{align} \] 即所有区间的 $ height$的最小值。暴力求解显然会 TLE。

枚举区间的结尾 \(i\),在这之前比 \(height[i]\) 大的值都不会对答案产生影响,考虑维护一个 \(height\) 单调栈(说来在这道题里,它只进不出的,说单调队列也没错。。。)记录 \(i\)

当考虑到 \(i\) 对答案的贡献时,记在 \(i\) 之前第一个满足 \(height[j] \leqslant height[i]\)\(j\),区间开头在 \([j + 1, \; i]\) 内的区间的最小值均为 \(height[i]\),即对答案的贡献为 \((i - j) \times height[i]\)。从头枚举一遍即可。

代码

就是这道题,让我换了后缀数组的版子,因为,这个版子理解起来容易一些(后缀数组的代码终于不用背了!)。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>
#include <stack>
const int MAXN = 500005;
namespace SuffixArray {
int rank[MAXN], sa[MAXN], height[MAXN], n;
char str[MAXN];
void buildSA(int m) {
static int fir[MAXN], sec[MAXN], temp[MAXN], cnt[MAXN], i;
n = strlen(str) + 1;
str[n - 1] = 0;
memset(cnt, 0, sizeof cnt);
for (i = 0; i < n; i++) cnt[(int) str[i]]++;
for (i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for (i = 0; i < n; i++) rank[i] = cnt[(int) str[i]] - 1;
for (int l = 1; l < n; l <<= 1) {
for (int i = 0; i < n; i++)
fir[i] = rank[i], sec[i] = i + l < n ? rank[i + l] : 0;
memset(cnt, 0, sizeof cnt);
for (i = 0; i < n; i++) cnt[sec[i]]++;
for (i = 1; i < n; i++) cnt[i] += cnt[i - 1];
for (i = n - 1; ~i; i--) temp[--cnt[sec[i]]] = i;
memset(cnt, 0, sizeof cnt);
for (i = 0; i < n; i++) cnt[fir[i]]++;
for (i = 1; i < n; i++) cnt[i] += cnt[i - 1];
for (i = n - 1; ~i; i--) sa[--cnt[fir[temp[i]]]] = temp[i];
bool unique = true;
rank[sa[0]] = 0;
for (i = 1; i < n; i++) {
rank[sa[i]] = rank[sa[i - 1]];
if (fir[sa[i]] == fir[sa[i - 1]] && sec[sa[i]] == sec[sa[i - 1]])
unique = false;
else rank[sa[i]]++;
}
if (unique) break;
}
}
void getHeight() {
int k = 0;
for (int i = 0; i < n - 1; i++) {
k ? k-- : 0;
int j = sa[rank[i] - 1];
while (str[i + k] == str[j + k]) k++;
height[rank[i]] = k;
}
}
}
int main() {
char *str = SuffixArray::str;
scanf("%s", str);
int n = strlen(str);
SuffixArray::buildSA(128);
SuffixArray::getHeight();
int *height = SuffixArray::height + 1;
long long ans = 0;
std::stack<int> s;
s.push(0);
static long long f[MAXN];
for (int i = 1; i < n; i++) {
while (!s.empty() && height[s.top()] > height[i]) s.pop();
ans += f[i] = f[s.top()] + (long long) (i - s.top()) * height[i];
s.push(i);
}
printf("%lld\n", (long long) (n - 1) * n * (n + 1) / 2 - 2 * ans);
return 0;
}