题目链接：UOJ 131
一年一度的「幻影阁夏日品酒大会」隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发「首席品酒家」和「首席猎手」两个奖项，吸引了众多品酒师参加。
在大会的晚餐上，调酒师 Rainbow 调制了 $n$ 杯鸡尾酒。这 $n$ 杯鸡尾酒排成一行，其中第 $i$ 杯酒 （$1 \le i \le n$） 被贴上了一个标签 $s_i$，每个标签都是 $26$ 个小写英文字母之一。设 $\text{Str}(l, r)$ 表示第 $l$ 杯酒到第 $r$ 杯酒的 $r − l + 1$ 个标签顺次连接构成的字符串。若 $\text{Str}(p, p_0) = \text{Str}(q, q_0)$，其中 $1 \le p \le p_0 \le n$，$1 \le q \le q_0 \le n$，$p \ne q$，$p_0 − p + 1 = q_0 − q + 1 = r$，则称第 $p$ 杯酒与第 $q$ 杯酒是「$r$ 相似」的。当然两杯「$r$ 相似」（$r > 1$）的酒同时也是「$1$ 相似」、「$2$ 相似」、$\dots$、「$(r − 1)$ 相似」的。特别地，对于任意的 $1 \le p, q \le n$，$p \ne q$，第 $p$ 杯酒和第 $q$ 杯酒都是「$0$ 相似」的。
在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了「首席品酒家」的称号，其中第 $i$ 杯酒 （$1 \le i \le n$） 的美味度为 $a_i$。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 $p$ 杯酒与第 $q$ 杯酒调兑在一起，将得到一杯美味度为 $a_p \cdot a_q$ 的酒。现在请各位品酒师分别对于 $r = 0, 1, 2, \dots, n − 1$，统计出有多少种方法可以选出两杯「$r$ 相似」的酒，并回答选择两杯「$r$ 相似」的酒调兑可以得到的美味度的最大值。
数据范围：$1 \le n \le 3 \times 10 ^ 5$，$\lvert a_i \rvert \le 10 ^ 9$。
Solution
题目中已经说明了本题的关键：
两杯「$r$ 相似」（$r > 1$）的酒同时也是「$1$ 相似」、「$2$ 相似」、$\dots$、「$(r − 1)$ 相似」的。
这启发我们从大到小枚举相似度，然后用并查集合并。具体实现为：先建立后缀数组，将所有后缀按照 $height$ 从大到小排序，维护每个集合内的最大值、最小值和答案。对于第一问，我们对每种相似度的答案做后缀和；对于第二问，我们对每种相似度的答案做后缀 $\max$。
时间复杂度：$\mathcal O(n \log n)$。
Code
#include <cstdio>
#include <algorithm>
const int N = 3e5 + 5;
const long long INF = 0x7f7f7f7f7f7f7f7f;
int n, a[N], fa[N], siz[N], id[N], mx[N], mn[N];
long long ret[N], ans1[N], ans2[N];
char s[N];
template <int MAX>
struct SuffixArray {
static const int N = MAX;
int n, m, sa[N], rk[N], cnt[N], tmp[N], height[N];
void radixSort() {
std::fill(cnt + 1, cnt + m + 1, 0);
for (int i = 1; i <= n; i++) cnt[rk[i]]++;
for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
}
template <typename Tp>
void build(Tp *a, int _n, int _m) {
n = _n, m = _m;
for (int i = 1; i <= n; i++) rk[i] = a[i], tmp[i] = i;
radixSort();
for (int l = 1, p = 0; p < n; l <<= 1, m = p) {
p = 0;
for (int i = n - l + 1; i <= n; i++) tmp[++p] = i;
for (int i = 1; i <= n; i++) if (sa[i] > l) tmp[++p] = sa[i] - l;
radixSort();
std::swap(rk, tmp);
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; i++) {
int u = sa[i - 1], v = sa[i];
int uu = (u + l <= n ? u + l : 0), vv = (v + l <= n ? v + l : 0);
rk[sa[i]] = (tmp[u] == tmp[v] && tmp[uu] == tmp[vv] ? p : ++p);
}
}
a[n + 1] = 0;
for (int i = 1, k = 0; i <= n; i++) {
k -= (k > 0);
int j = sa[rk[i] - 1];
for (; a[i + k] == a[j + k]; k++);
height[rk[i]] = k;
}
}
};
SuffixArray<N> S;
template <typename Tp>
void cmax(Tp &x, Tp y) {
x < y && (x = y);
}
template <typename Tp>
void cmin(Tp &x, Tp y) {
x > y && (x = y);
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y, int len) {
fa[y = find(y)] = x = find(x);
ans1[len] += 1LL * siz[x] * siz[y];
siz[x] += siz[y];
cmax(ret[x], ret[y]);
cmax(ret[x], std::max(1LL * mx[x] * mx[y], 1LL * mn[x] * mn[y]));
cmax(ret[x], std::max(1LL * mx[x] * mn[y], 1LL * mn[x] * mx[y]));
cmax(mx[x], mx[y]);
cmin(mn[x], mn[y]);
cmax(ans2[len], ret[x]);
}
int main() {
scanf("%d%s", &n, s + 1);
S.build(s, n, 255);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
fa[i] = id[i] = i, siz[i] = 1;
mx[i] = mn[i] = a[i], ret[i] = -INF;
}
std::fill(ans2, ans2 + n, -INF);
std::sort(id + 2, id + n + 1, [](int x, int y) {
return S.height[x] > S.height[y];
});
for (int i = 2; i <= n; i++) {
merge(S.sa[id[i]], S.sa[id[i] - 1], S.height[id[i]]);
}
for (int i = n - 2; i >= 0; i--) {
ans1[i] += ans1[i + 1];
ans2[i] = std::max(ans2[i], ans2[i + 1]);
}
for (int i = 0; i < n; i++) {
printf("%lld %lld\n", ans1[i], ans1[i] ? ans2[i] : 0LL);
}
return 0;
}