Luogu

[LOJ](https://loj.ac/problem/2133）

分析

如果两个位置是 $r$ 相似的，则它们也是 $k\in[0,r)$ 相似的。我们可以只求出 LCP 为 $r$ 时的答案，再求一遍后缀和/后缀 max 即可得到答案。

考虑两个位置的 LCP 实际上是一段区间的 $height$ 的最小值。我们可以将 $height_i$ 从大到小排序，每次加入一个 $height_i$ 相当于合并了排名相邻的两个后缀，可以用并查集维护，则一个连通块内的元素满足两两间的 LCP $\geq height_i$。

对于第一问，合并时可以随意选择左右两边后缀所在连通块中的某个后缀，所以产生 $sz_x\times sz_y$ 的贡献；对于第二问，维护最小值和最大值即可（因为可能有负数）。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,a[N]; char s[N];

int sa[N],rk[N],height[N],x[N],y[N],z[N];
void SuffixSort() {
    int m=122;
    for (int i=1;i<=n;++i) ++z[x[i]=s[i]];
    for (int i=2;i<=m;++i) z[i]+=z[i-1];
    for (int i=n;i;--i) sa[z[x[i]]--]=i;
    for (int k=1;k<=n;k<<=1) {
        int p=0;
        for (int i=n-k+1;i<=n;++i) y[++p]=i;
        for (int i=1;i<=n;++i) if (sa[i]>k) y[++p]=sa[i]-k;
        for (int i=1;i<=m;++i) z[i]=0;
        for (int i=1;i<=n;++i) ++z[x[i]];
        for (int i=2;i<=m;++i) z[i]+=z[i-1];
        for (int i=n;i;--i) sa[z[x[y[i]]]--]=y[i],y[i]=0;
        swap(x,y),x[sa[1]]=p=1;
        for (int i=2;i<=n;++i)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p:++p;
        if (p==n) break; m=p;
    }
}
void GetHeight() {
    for (int i=1;i<=n;++i) rk[sa[i]]=i;
    for (int i=1,j=0;i<=n;++i) {
        if (j) --j; int k=sa[rk[i]-1];
        while (s[i+j]==s[k+j]) ++j;
        height[rk[i]]=j;
    }
}

ll ans1[N],ans2[N];
struct node { int h,x,y; } q[N];
bool cmp(node a,node b) { return a.h>b.h; }

int f[N],sz[N],mx[N],mn[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
void merge(int x,int y,int l) {
    x=find(x),y=find(y);
    if (x!=y) {
        ans1[l]+=1ll*sz[x]*sz[y];
        ans2[l]=max(ans2[l],max(1ll*mx[x]*mx[y],1ll*mn[x]*mn[y]));
        f[y]=x,sz[x]+=sz[y],mx[x]=max(mx[x],mx[y]),mn[x]=min(mn[x],mn[y]);
    }
}

int main() {
    n=read(); scanf("%s",s+1);
    for (int i=1;i<=n;++i) a[i]=read();
    SuffixSort(); GetHeight();
    for (int i=1;i<=n;++i) f[i]=i,sz[i]=1,mx[i]=mn[i]=a[sa[i]];
    for (int i=2;i<=n;++i) q[i-1]=(node){height[i],i-1,i};
    sort(q+1,q+n,cmp); memset(ans2,0xc0,sizeof(ans2));
    for (int i=1;i<n;++i) merge(q[i].x,q[i].y,q[i].h);
    for (int i=n;~i;--i) ans1[i]+=ans1[i+1],ans2[i]=max(ans2[i],ans2[i+1]);
    for (int i=0;i<n;++i) printf("%lld %lld\n",ans1[i],ans1[i]?ans2[i]:0);
    return 0;
}