题意：若两个字符开始的后面r个字符都一样，则称这两个字符是r相似的。它们也是r-1相似的。
对于r∈[0,n)分别求有多少种方案，其中权值最大方案权值是多少。此处权值是选出的两个字符的权值之积。
解：后缀自动机吊打后缀数组！！！
先看第一问，我们考虑后缀自动机上每个节点的贡献。显然cnt>1的节点才会有贡献。
它会对r ∈ len[fail[x]] + 1 ~ len[x]这一段的答案产生C(cntx，2)的贡献。这就是一个区间加法。
有个小问题，如果r减少那么相应的可选的其实会变多，但是此处我们不统计，那些会在以另一个字符结尾的别的节点上考虑到。
这样第一问就解决了。第二问？发现问题很大...一个节点的每个串都是结尾相同，开头不同。那么开头的权值之积就不好维护。
因为结尾相同，所以考虑反着建后缀自动机，然后就变成了开头相同了。那么如何维护乘积最大值呢？
考虑到一个节点的末尾所在位置，也就是它的right集合。显然就是fail树的子树中所有在主链上的节点。
于是每个点维护子树最大值即可。因为有负数所以还要最小值。
这样一个节点对第二问的贡献就是区间取max了。这两问的操作都可以用线段树搞定。
#include <cstdio>
#include <cstring>
#include <algorithm> typedef long long LL;
const int N = ; int tr[N][], tot = , fail[N], len[N], cnt[N], bin[N], topo[N], last = , val[N], n;
int max1[N], max2[N], min1[N], min2[N];
char str[N];
LL tag[N << ], large[N << ]; inline void insert(char c) {
int f = c - 'a';
int p = last, np = ++tot;
last = np;
len[np] = len[p] + ;
cnt[np] = ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
int nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = fail[np] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
}
}
return;
} inline void update(int x, int y) {
int t[];
t[] = max1[x];
t[] = max2[x];
t[] = max1[y];
t[] = max2[y];
std::sort(t, t + );
max1[x] = t[];
max2[x] = t[];
t[] = min1[x];
t[] = min2[x];
t[] = min1[y];
t[] = min2[y];
std::sort(t, t + );
min1[x] = t[];
min2[x] = t[];
return;
} inline void prework() {
for(int i = ; i <= tot; i++) {
bin[len[i]]++;
}
for(int i = ; i <= tot; i++) {
bin[i] += bin[i - ];
}
for(int i = ; i <= tot; i++) {
topo[bin[len[i]]--] = i;
}
for(int i = tot; i >= ; i--) {
int a = topo[i];
cnt[fail[a]] += cnt[a];
update(fail[a], a);
}
return;
} inline void pushdown(int o) {
if(tag[o]) {
tag[o << ] += tag[o];
tag[o << | ] += tag[o];
tag[o] = ;
}
large[o << ] = std::max(large[o << ], large[o]);
large[o << | ] = std::max(large[o << | ], large[o]);
return;
} void add(int L, int R, LL v, int l, int r, int o) {
if(L <= l && r <= R) {
tag[o] += v;
return;
}
int mid = (l + r) >> ;
pushdown(o);
if(L <= mid) {
add(L, R, v, l, mid, o << );
}
if(mid < R) {
add(L, R, v, mid + , r, o << | );
}
return;
} void out(int l, int r, int o) {
if(l == r) {
if(r != n) {
printf("%lld %lld \n", tag[o], tag[o] ? large[o] : );
}
return;
}
int mid = (l + r) >> ;
pushdown(o);
out(l, mid, o << );
out(mid + , r, o << | );
return;
} void change(int L, int R, LL v, int l, int r, int o) {
if(v <= large[o]) {
return;
}
if(L <= l && r <= R) {
large[o] = v;
return;
}
int mid = (l + r) >> ;
pushdown(o);
if(L <= mid) {
change(L, R, v, l, mid, o << );
}
if(mid < R) {
change(L, R, v, mid + , r, o << | );
}
return;
} int main() {
memset(max1, ~0x3f, sizeof(max1));
memset(max2, ~0x3f, sizeof(max2));
memset(min1, 0x3f, sizeof(min1));
memset(min2, 0x3f, sizeof(min2));
memset(large, ~0x3f, sizeof(large));
scanf("%d", &n);
scanf("%s", str + );
int l1 = -0x3f3f3f3f, l2 = -0x3f3f3f3f, s1 = 0x3f3f3f3f, s2 = 0x3f3f3f3f;
for(int i = ; i <= n; i++) {
scanf("%d", &val[i]);
if(l1 < val[i]) {
l2 = l1;
l1 = val[i];
}
else if(l2 < val[i]) {
l2 = val[i];
}
if(s1 > val[i]) {
s2 = s1;
s1 = val[i];
}
else if(s2 > val[i]) {
s2 = val[i];
}
}
for(int i = n; i >= ; i--) {
insert(str[i]);
max1[last] = min1[last] = val[i];
}
prework();
//
for(int i = ; i <= tot; i++) {
if(cnt[i] < ) {
continue;
}
// len[fail[i]] + 1 ~ len[i]
add(len[fail[i]] + , len[i], 1ll * cnt[i] * (cnt[i] - ) / , , n, );
change(len[fail[i]] + , len[i], std::max(1ll * max1[i] * max2[i], 1ll * min1[i] * min2[i]), , n, );
} printf("%lld %lld \n", 1ll * n * (n - ) / , std::max(1ll * l1 * l2, 1ll * s1 * s2));
out(, n, );
return ;
}
AC代码