题意：给一个长度为n的字符串S。若两个后缀p、q（p≠q）存在长度为r的公共前缀，则称p、q是“r相似”的。每个后缀有权值ai。对于r=0,1,..n-1，求出有多少对r相似的后缀（无序），并求出每对r相似后缀权值之积的最大值。
这道题有不少做法。 出题人是lydrainbowcat神犇，但是在某培训班他讲这道题的时候并不知道他就是这个ID的主人......
当时没听懂，不过记住了可以用后缀数组。现在自己做出来啦。
首先，“r相似”的后缀对同时是“(r-1)相似”、“(r-2)相似”、......、“0相似”的；对于(p, q)，不妨先只将它统计进LCP(p, q)，最后求个后缀和。其次，本题有两问，先解决第一问。
以什么样的顺序统计对数呢？对于(p, q)，设p<q，可以枚举q，统计有多少个p，还要把这一对归到某一类中。对后缀排个序，则
方便起见，下面为所有后缀更名，改为后缀数组中的rank。
怎样避免r的枚举呢？由min函数的单调性，LCP是呈阶梯状下降的。可以求出i之前与i离的最近的height小于i的位置，也就是台阶的边缘，设为p[i]，则p[i]前面的那些后缀j满足LCP(j, i) = LCP(j, p[i])。它们由i或p[i]统计是等效的。在每个位置设一计数器t[i]，表示该处及右边有多少个后缀于此处统计它的另一半， 则区间[p[i], i)中的贡献为ans[height[i]] += (i-p[i])*t[i]。可以模拟标记在树上push的过程，t[p[i]] += t[i]，统计区间[1, p[i])中的贡献。从右往左跑一遍即可。
受到CODEVS 1404 字符串匹配的启发。这是一道不错的题，不仅仅是KMP的模板题。BTW，前几天发现这题也可以用exKMP来做。
第二问，怎么求权值之积的最大值？基本思路是用一边的最大值乘另一边的最大值，用一边的最小值乘另一边的最小值。沿用上面第一问的框架。对每个位置i记录mn[i]、mx[i]，表示push到此处的后缀的权值的最小值和最大值。用[p[i], i)的区间最值和mn[i]、mx[i]相乘，更新答案，并将mn[i]和mx[i]向前push。涉及静态区间最值查询，可以使用ST表。注意我们已经将后缀更名，构建时不要用读入的a[i]，而是a[sa[i]]，sa是后缀数组。
- 构造后缀数组和ST表。
。 - 单调栈求p数组。
。 - 统计答案。
。 - 后缀和。
。
总共
找出了当时讲课的课件，发现我的思路和出题人不一样，但是与算法一殊途同归。还有一种使用并查集的算法二，简述如下：
对于height的最大值r1，只有sa上连续一段的height值均为r1时，这一段后缀才两两r1相似。统计答案即可。对于小于r1的r，这些height不影响区间最小值，所以把它们合并。新的height有最大值r2，以此类推。用并查集维护。这个思路的核心是从大到小枚举r。时间复杂度同样为
后缀自动机也可以做，待我学习一番。
#include <cstdio>
#include <algorithm>
#include <queue>
typedef long long ll;
const int MAX_N = 3e5;
const ll inf = 1LL<<61;
using std::fill_n;
using std::swap;
using std::min;
using std::max;
namespace SA {
int sa[MAX_N+1], buf[2][MAX_N+2], h[MAX_N+1], c[MAX_N+1], *rk, *t;
void build(char s[], int n)
{
int i, j, l;
rk = buf[0];
t = buf[1];
++n;
// fill_n(c, 'z'+1, 0);
for (i = 1; i <= n; ++i) ++c[s[i]];
for (i = 1; i <= 'z'; ++i) c[i] += c[i-1];
for (i = n; i >= 1; --i) sa[--c[s[i]]] = i;
int m = rk[sa[0]] = 0;
for (i = 1; i < n; ++i) rk[sa[i]] = m += s[sa[i]] != s[sa[i-1]];
for (l = 1; ++m < n; l *= 2) {
for (i = 0; i < l; ++i) t[i] = n-l+1+i;
for (j = 0; j < n; ++j) if (sa[j] > l) t[i++] = sa[j]-l;
fill_n(c, m, 0);
for (i = 1; i <= n; ++i) ++c[rk[i]];
for (i = 1; i < n; ++i) c[i] += c[i-1];
for (i = n-1; i >= 0; --i) sa[--c[rk[t[i]]]] = t[i];
swap(rk, t);
m = rk[sa[0]] = 0;
for (i = 1; i < n; ++i)
rk[sa[i]] = m += t[sa[i]] != t[sa[i-1]] || t[sa[i]+l] != t[sa[i-1]+l];
}
for (i = 1, j = 0; i < n; h[rk[i]] = j, j -= j>0, ++i)
for (int p = sa[rk[i]-1]; s[p+j] == s[i+j]; ++j) ;
}
};
namespace ST {
const int MAX_D = 19;
ll mn[MAX_D+1][MAX_N+1], mx[MAX_D+1][MAX_N+1];
void build(ll a[], int n)
{
for (int i = 1; i <= n; ++i)
mn[0][i] = mx[0][i] = a[SA::sa[i]];
for (int i = 1, l = 1; l*2 <= n; ++i, l *= 2)
for (int j = 2*l; j <= n; ++j) {
mn[i][j] = min(mn[i-1][j], mn[i-1][j-l]);
mx[i][j] = max(mx[i-1][j], mx[i-1][j-l]);
}
}
void query(int l, int r, ll& a, ll& b) // [l, r] min max
{
int i = 0;
while ((1 << i+1) < r-l+1) ++i;
a = min(mn[i][r], mn[i][l+(1<<i)-1]);
b = max(mx[i][r], mx[i][l+(1<<i)-1]);
}
};
char s[MAX_N+2];
ll a[MAX_N+1], c[MAX_N], d[MAX_N], mn[MAX_N+1], mx[MAX_N+1];
int S[MAX_N+1], p[MAX_N+1], t[MAX_N+1];
template<typename T>
T relax(T& x, T v) { return x = min(x, v); }
template<typename T>
T tension(T& x, T v) { return x = max(x, v); }
int main()
{
using SA::h;
int n;
scanf("%d %s", &n, s+1);
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
SA::build(s, n);
ST::build(a, n);
int top = 0;
h[1] = -1;
for (int i = n; i >= 1; --i) {
while (top && h[i] < h[S[top-1]])
p[S[--top]] = i;
S[top++] = i;
}
fill_n(d, n, -inf);
for (int i = 1; i <= n; ++i)
mn[i] = mx[i] = a[SA::sa[i]];
for (int i = n; i > 1; --i) {
int pre = p[i];
t[pre] += ++t[i];
c[h[i]] += (ll)(i-pre)*t[i];
ll x, y;
ST::query(pre, i-1, x, y);
tension(d[h[i]], max(x*mn[i], y*mx[i]));
tension(mx[pre], mx[i]);
relax(mn[pre], mn[i]);
}
for (int i = n-2; i >= 0; --i) {
c[i] += c[i+1];
tension(d[i], d[i+1]);
}
for (int i = 0; i < n; ++i)
printf("%lld %lld\n", c[i], c[i] ? d[i] : 0);
return 0;
}