BZOJ 4199
题意：见上。
40分即枚举两个点Hash即可。
50分改为枚举长度+一个点，Hash即可。
考虑100分情况
我们发现两个答案都是都是递减的，所以我们可以逆向求答案。(后缀和过程)
这题显然是要用后缀数组了
我们将$height$值一样的存在一个vector里，然后按照$height$值倒着求答案。
附上样例一说明，SA后我们会得到如下的信息：
i height sa stringsai asai
1 0 10 i 7
2 1 5 iiipoi 4
3 2 6 iipoi 8
4 1 7 ipoi 3
5 0 3 noiiipoi 4
6 0 9 oi 4
7 2 4 oiiipoi 7
8 1 2 onoiiipoi 1
9 0 8 poi 6
10 2 1 ponoiiipoi2
具体可以看xht 37 大佬的题解
这里直接讲并查集做法，即每次找一个位置，就把他和$SA$序上$i-1$位和$i$位的位置在并查集上合并，那么下次找的话，就可以直接统计两个连通块的信息。
并查集维护集合大小，集合最大值最小值(有负数存在，所以最大乘积可能来自最小值)，以上从上面的表格中可以分析出来
知识点
1、注意不要将SA的任何字符映射到0
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 300000 + 5;
const LL INF = 1e18 + 2;
char ch[MAXN];
int a[MAXN], n, m, v[MAXN];
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
void build() {//构造后缀数组
for (int i = 1; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;//基数排序排第一轮
for (int k = 1; k <= n; k <<= 1) {
int p = 0;
for (int i = n - k + 1; i <= n; i++) tp[++p] = i;//(n-k)~(n-1)无第二关键字，所以排序应该排在前面
for (int i = 1; i <= n; i++) if (SA[i] > k) tp[++p] = SA[i] - k;
//只有SA[i]>=k的SA[i]才是第二关键字的位置
//从图中可以看出第一关键字和第二关键字的位置相差k，故SA[i] - k
for (int i = 1; i <= m; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名
for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];//保证了第一关键字的顺序再排第二关键字
//基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标)
swap(rk, tp);//此时tp没用，暂存上一轮rank的值
p = 1, rk[SA[1]] = 1;
for (int i = 2; i <= n; ++i)
rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
//算排名第i的数的rank，按sa顺序能够保证rank的正确性，但是要cmp判断与上一个字符串相等的情况
if (p >= n) break;//剪枝，已经没有重复元素
m = p;
}
int k = 0;//k是比i-1前一名的后缀
for (int i = 1; i <= n; ++i) {//H[0], H[1], H[2] ...的顺序计算
if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
int j = SA[rk[i] - 1]; //前一名的后缀位置
while (ch[i + k] == ch[j + k]) k++; //往后比较
height[rk[i]] = k; //更新答案
}
}
int f[MAXN], maxd[MAXN], mind[MAXN], sz[MAXN];
LL mp[MAXN], ans1, ans2, fans[MAXN][2];
vector<int > vec[MAXN];
int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);}
void merge(int x, int y) {
if (sz[x] > sz[y]) swap(x, y);
f[x] = y;
ans1 += 1ll * sz[x] * sz[y];
sz[y] += sz[x];
mp[y] = max(mp[y], max(1ll * maxd[x] * maxd[y], 1ll * mind[x] * mind[y]));
maxd[y] = max(maxd[x], maxd[y]);
mind[y] = min(mind[x], mind[y]);
ans2 = max(ans2, mp[y]);
}
void clean() {
ms(fans, 0), m = 30;
}
int solve() {
clean();
cin >> n;
scanf("%s", ch + 1);
for (int i = 1; i <= n; ++i) scanf("%d", &v[i]), a[i] = ch[i] - 'a' + 1;
build();
for (int i = 1; i <= n; ++i) {
f[i] = i, sz[i] = 1;
maxd[i] = mind[i] = v[SA[i]];
mp[i] = -INF;
}
ans1 = 0, ans2 = -INF;
for (int i = 1; i <= n; ++i) vec[height[i]].push_back(i);
for (int len = n - 1; len >= 0; --len) {
for (int i = 0; i < (int)vec[len].size(); ++i) {
int u = vec[len][i];
merge(find(u), find(u - 1));
if (ans1)
fans[len][0] = ans1, fans[len][1] = ans2;
}
}
for (int i = 0; i < n; ++i) printf("%lld %lld\n", fans[i][0], fans[i][1]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
4
aaaa
1 1 1 1
*/
