解题思路
??从后缀数组的角度考虑，利用\(lcp\)的性质，\(lcp(i, j) = min(lcp(k_1, k_2), i \neq k_1,k_2 \neq j\)。那么对于所有“r相似”的后缀来说他们之间的\(lcp\)肯定是大于等于\(r\)的。我们可以考虑根据lcp的大小按顺序将所有后缀加入集合，从而维护一系列lcp大于等于r的集合进而求得所有符合条件的后缀对数，这就是经典的并查集维护集合问题。
代码
const int maxn = 3e5+10;
char s[maxn];
int n, m;
int sa[maxn], x[maxn], y[maxn], c[maxn], rk[maxn], h[maxn];
void get_sa() {
for (int i = 1; i<=n; ++i) ++c[x[i]=s[i]];
for (int i = 2; i<=m; ++i) c[i] += c[i-1];
for (int i = n; i; --i) sa[c[x[i]]--] = i;
for (int k = 1; k<=n; k<<=1) {
int num = 0;
for (int i = n-k+1; i<=n; ++i) y[++num] = i;
for (int i = 1; i<=n; ++i)
if (sa[i]>k) y[++num] = sa[i]-k;
for (int i = 1; i<=m; ++i) c[i] = 0;
for (int i = 1; i<=n; ++i) ++c[x[i]];
for (int i = 1; i<=m; ++i) c[i] += c[i-1];
for (int i = n; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y);
x[sa[1]] = 1, num = 1;
for (int i = 2; i<=n; ++i)
x[sa[i]] = (y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) ? num : ++num;
if (num==n) break;
m = num;
}
}
vector<P> g[maxn];
void get_h() {
for (int i = 1; i<=n; ++i) rk[sa[i]] = i;
for (int i = 1, k = 0; i<=n; ++i) {
if (rk[i]==1) continue;
if (k) --k;
int j = sa[rk[i]-1];
while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) ++k;
h[rk[i]] = k;
g[k].push_back({sa[rk[i]], sa[rk[i]-1]});
}
}
int p[maxn];
ll sz[maxn], mx1[maxn], mx2[maxn], mi1[maxn], mi2[maxn];
int fd(int x) {
return p[x]==x ? p[x]:p[x]=fd(p[x]);
}
ll sum = 0, ans = -2e18;
void calc(int x) {
for (auto t :g[x]) {
int fa = fd(t.x);
int fb = fd(t.y);
if (fa!=fb) {
sum += 1LL*sz[fa]*sz[fb];
p[fa] = fb;
sz[fb] += sz[fa];
if (mx1[fa]>=mx1[fb]) mx2[fb] = max(mx1[fb], mx2[fa]), mx1[fb] = mx1[fa];
else if (mx1[fa]>mx2[fb]) mx2[fb] = mx1[fa];
if (mi1[fa]<=mi1[fb]) mi2[fb] = min(mi1[fb], mi2[fa]), mi1[fb] = mi1[fa];
else if (mi1[fa]<mi2[fb]) mi2[fb] = mi1[fa];
ans = max({ans, 1LL*mx1[fb]*mx2[fb], 1LL*mi1[fb]*mi2[fb]});
}
}
}
int main() {
IOS;
cin >> n, m = 122;
cin >> s+1;
get_sa(); get_h();
for (int i = 1; i<=n; ++i) {
cin >> mx1[i];
mi1[i] = mx1[i];
mx2[i] = -2e18, mi2[i] = 2e18;
p[i] = i, sz[i] = 1;
}
vector<P> t;
for (int i = n-1; i>=0; --i) {
calc(i);
t.push_back({sum, ans<-1.5e18 ? 0:ans});
}
for (int i = t.size()-1; i>=0; --i) cout << t[i].x << ‘ ‘ << t[i].y << endl;
return 0;
}