0%

「SDOI 2016」生成魔咒

很有意思的题,做完感觉脑子里一根筋又被拨回正轨了。

考虑一个做本质不同子串的通用思路。将该串的所有后缀排序,并统计$\sum{n - sa_i + height_i}$即可。

这样做本质上是容斥。但这个容斥与别人不同,他通过字典序来贪心地保证了答案正确,而不像随便一个顺序,那样的话不会容斥完全。

那么本题就有了些许做法了。

考虑先reverse一下这个串,这样的话后缀数组仅仅是增加一个量,也就有可能被我们维护。

进一步地去想,如果我们离线地先将后缀数组build出来,那么每次在这个串里面添加一个字符,就等价于添加一个后缀,就等价于往已经排好序的后缀“空”里面“填”。

这样就很简单了,搞个set来维护所有后缀排序后的下标,每次找前驱后继更新一下lcp之和即可。

注意两个后缀的lcp就是$i=rk_i,j=rk_j$后的区间height的min,这个可以st表做到$\mathcal{O(1)}$.

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>

#define test(...) fprintf(stderr, __VA_ARGS__)
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;

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

const int N = 100010 + 5;
int sa[N], rk[N], rk_[N], id[N], px[N], cnt[N], h[N], n, a[N], b[N], SZ, LG[N];
int rmq[N][20];
struct node {
int x;
node(int x=0):x(x){}
bool operator < (const node& rhs) const {
return rk[x] < rk[rhs.x];
}
};
bool cmp(int x, int y, int w) {
return rk_[x] == rk_[y] && rk_[x + w] == rk_[y + w];
}
void re_order() {
for (int i = 1; i <= n; ++i) b[i] = a[i];
sort (b + 1, b + n + 1);
SZ = unique(b + 1, b + n + 1) - (b + 1);
for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + SZ + 1, a[i]) - b;
}
void get_suffix_array() {
int i, j, m = SZ, p, w;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = a[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; i <= n; ++i) rk[sa[i]] = i;
for (i = 1, j = 0; i <= n; ++i) {
if (rk[i] == 1) continue;
while (a[i + j] == a[sa[rk[i] - 1] + j]) ++j;
h[rk[i]] = j;
rmq[rk[i]][0] = j;
if (j) --j;
}
}
int lcp(int i, int j) {
i = rk[i], j = rk[j];
if (i > j) swap(i, j);
++i;
int depth = LG[j - i];
return min(rmq[i][depth], rmq[j - (1 << depth) + 1][depth]);
}
void solve() {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 2; i <= n; ++i) LG[i] = LG[i >> 1] + 1;
reverse(a + 1, a + n + 1);
re_order();
get_suffix_array();
for (int j = 1; j <= 20; ++j)
for (int i = 1; i <= n; ++i) {
if (i + (1 << j) - 1 > n) break;
rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
}
rk[0] = 0;
rk[n + 1] = n + 1;
set <node> st;
st.insert(0);
st.insert(n + 1);
ll sum_lcp = 0;
ll total_length = 0;
for (int i = 1; i <= n; ++i) {
int pos = n - i + 1;
set <node> :: iterator it = st.lower_bound(node(pos));
int nxt = (*it).x, prf = (*(--it)).x;
sum_lcp += lcp(prf, nxt);
sum_lcp -= lcp(prf, pos);
sum_lcp -= lcp(pos, nxt);
total_length += i;
st.insert(node(pos));
printf ("%lld\n", total_length + sum_lcp);
}
}

int main() {
int tests = 1;
while (tests--)
solve();
return 0;
}