题面：
给出一个n个字符的字符串，每个字符有一个权值，现在要求求出有多少种方法可以选出两个长度为r的相同的子串，以及能选出来的两个串首字符的权值的最大乘积。(可能描述的有点shi)
(Solution:)
因为子串是后缀的前缀，所以就自然地想到用后缀树数组。
因为两个 (k) 相似的串必定满足 (r) 相似 ((lle k)).
所以我们离线从大到小处理 (Height) 数组, 这样满足的 (height) 区间只会变大，不会变小，把这些后缀想象成一个个集合，然后就可以用带权并查集维护了。每次处理一个 (height) ，那么它关联到的两个后缀的前缀是满足条件的，于是 (merge) 这两个后缀(实际上是集合)。
还有一个很重要的地方是每次处理一个 (height) 时都只算了height相似的答案，而这个答案是会对之后处理的答案做出全部贡献的，即两个 (k) 相似的串必定满足 (r) 相似 ((lle k)).所以再做一遍前缀和，最大乘积就取 (max)。
(ps:别忘了维护最小值，因为负负得正)
(Source:)
#include <set>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;
#define fir first
#define sec second
#define pb push_back
#define mp make_pair
#define LL long long
#define INF (0x3f3f3f3f)
#define mem(a, b) memset(a, b, sizeof (a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(x) cout << #x << " = " << x << endl
#define tralve(i, x) for (register int i = head[x]; i; i = nxt[i])
#define For(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))
#define Forr(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define ____ debug("go
")
namespace io {
static char buf[1<<21], *pos = buf, *end = buf;
inline char getc()
{ return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }
inline int rint() {
register int x = 0, f = 1;register char c;
while (!isdigit(c = getc())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc()));
return x * f;
}
inline LL rLL() {
register LL x = 0, f = 1; register char c;
while (!isdigit(c = getc())) if (c == '-') f = -1;
while (x = (x << 1ll) + (x << 3ll) + (c ^ 48), isdigit(c = getc()));
return x * f;
}
inline void rstr(char *str) {
while (isspace(*str = getc()));
while (!isspace(*++str = getc()))
if (*str == EOF) break;
*str = ' ';
}
template<typename T>
inline bool chkmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }
template<typename T>
inline bool chkmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }
}
using namespace io;
const int N = 3e5 + 3;
int n;
namespace SA {
char str[N];
int sa[N], rk[N], ht[N], M;
void Rsort(int *buc, int *tp) {
fill(buc, buc + 1 + M, 0);
For (i, 1, n) buc[rk[i]] ++;
For (i, 1, M) buc[i] += buc[i - 1];
Forr (i, n, 1) sa[ buc[ rk[ tp[i] ] ] -- ] = tp[i];
}
void SuffixSort() {
static int buc[N], tp[N];
For (i, 1, n) chkmax(M, rk[i] = str[i - 1] - 'a' + 1), tp[i] = i;
Rsort(buc, tp);
for (register int len = 1, cnt = 0; cnt < n; len <<= 1, M = cnt) {
cnt = 0;
For (i, n - len + 1, n) tp[++cnt] = i;
For (i, 1, n) if (sa[i] - len > 0) tp[++cnt] = sa[i] - len;
Rsort(buc, tp); swap(rk, tp); rk[sa[1]] = cnt = 1;
For (i, 2, n) rk[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + len] == tp[sa[i - 1] + len] ? cnt : ++cnt);
}
}
void getHt() {
int len = 0;
For (i, 1, n) {
if (len) len --;
int j = sa[rk[i] - 1];
while (str[j + len - 1] == str[i + len - 1]) len ++;
ht[rk[i]] = len;
}
}
}
int size[N], fa[N], id[N];
LL Min[N], Max[N], sum[N], valmax[N], Ans[N];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void Merge(int x, int y, int len) {
x = find(x), y = find(y);
fa[y] = x;
sum[len] += 1ll * size[x] * size[y];
size[x] += size[y];
chkmax(valmax[x], max(valmax[x], valmax[y]));
chkmax(valmax[x], max(Min[x] * Min[y], Max[x] * Max[y]));
chkmin(Min[x], Min[y]);
chkmax(Max[x], Max[y]);
chkmax(Ans[len], valmax[x]);
}
int main() {
#ifndef ONLINE_JUDGE
file("SA");
#endif
n = rint();
rstr(SA::str);
SA::SuffixSort();
SA::getHt();
For (i, 1, n) {
fa[i] = id[i] = i;
size[i] = 1;
valmax[i] = Ans[i] = -1e18;
Min[i] = Max[i] = rint();
}
Ans[0] = Ans[n + 1] = -1e18;
sort(id + 1, id + 1 + n, [] (int a, int b) {return SA::ht[a] > SA::ht[b];});//按照height从大到小排序，id[i]为第i长的height的rk
For (i, 1, n)
Merge(SA::sa[id[i]], SA::sa[id[i] - 1], SA::ht[id[i]]);//合并 height 所关联的两个后缀
Forr (i, n - 1, 0)
sum[i] += sum[i + 1], chkmax(Ans[i], Ans[i + 1]);
For (i, 0, n - 1)
printf("%lld %lld
", sum[i], !sum[i] ? 0 : Ans[i]);
}