0%

「AHOI 2013」差异

注意观察某些独特的东西。

首先明确题目要我们求什么。看到后面的 $LCP(T_i, T_j)$ 很容易用后缀数组将其转化成 $\min_{rk[i] < k \leq rk[j]}{height[k]}$。$(若rk[i] < rk[j])$

考虑计算每个位置的h作为min出现的次数。很明显这个东西可以用单调栈一步求出来。那么就转为计算

$\sum_{p = l} ^ {i} \sum_{p1 = i} ^ {r} (n - sa[p - 1] + 1) + (n - sa[p1] + 1)$。

然后大家只要有脑子就可以发现上面那个式子加起来是$\sum_{i = 1} ^ {n} i * (n - 1)$,因为任何一个长度为$i$的后缀都会被计算$n-1$次。

那么这个题就做完了,注意单调栈的l,r求法并不相同,因为要考虑去掉重复。

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>

#pragma GCC optimize(2)

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;

int gi() {
int f = 1, x = 0; char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return f * x;
}

const int N = 500010;
int sa[N], rk[N], px[N], cnt[N], rk_[N], id[N], h[N], n;
int st[N], tp, l[N], r[N];
char s[N];
ll pref[N];
bool cmp(int x, int y, int w) {
return rk_[x] == rk_[y] && rk_[x + w] == rk_[y + w];
}
void get_SA() {
int i, j, m = 300, p, w;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
for (w = 1; w < n; w <<= 1, m = p) {
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
memcpy(rk_, rk, sizeof(rk));
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? p : ++p;
}
for (i = 1, j = 0; i <= n; ++i) {
if (rk[i] == 1) continue;
int pos = sa[rk[i] - 1];
while (s[i + j] == s[pos + j]) ++j;
h[rk[i]] = j;
if (j) --j;
}
// cout << "height: ";
// for (i = 1; i <= n; ++i) cout << h[i] << " ";
// cout << '\n';
}
ll SUM(ll l, ll r) {
return pref[r] - pref[l - 1];
}
int main() {
scanf ("%s", s + 1);
n = strlen(s + 1);
get_SA();
rep (i, 1, n) l[i] = 0, r[i] = n + 1;
for (int i = 1; i <= n; ++i) {
while (tp && h[st[tp]] >= h[i]) --tp;
if (tp) l[i] = st[tp];
st[++tp] = i;
}
tp = 0;
for (int i = n; i >= 1; --i) {
while (tp && h[st[tp]] > h[i]) --tp;
if (tp) r[i] = st[tp];
st[++tp] = i;
}
for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + sa[i];
ll ans = 0, ANS = 0;
for (int i = 1; i <= n; ++i) ans += 1LL * i * (n - 1);
for (int i = 1; i <= n; ++i) {
int seg_l = l[i] + 1, seg_r = r[i] - 1;
ll ways = (i - seg_l + 1) * 1ll * (seg_r - i + 1);
ANS += ways;
ans += -2LL * h[i] * ways;
}
cout << ans << '\n';
return 0;
}