题意

给一个字符串 $s$，每个位置有一个权值 $a$，可以是负数。记 $s[i\cdots n]$ 和 $s[j\cdots n]$ 的最长公共前缀为 $lcp(i,j)$，则对于 $r=0,1,\cdots n-1$，求 $\sum_{0\leq i<j<n}[lcp(i,j)\geq r]$ 和 $\max_{0\leq i<j<n,lcp(i,j)\geq r}a_ia_j$。

题解

看到后缀 lcp 先无脑对反串建个 SAM。

考虑在后缀树上更新答案，考虑从一个后缀所在的节点开始往上跳，那么每个点代表了这个后缀的长度为 $[len_{link_k}+1,len_k]$ 的前缀。那么我们第一问在建 SAM 的时候给每个后缀所在节点打一个标记，然后维护子树内标记和；第二问的答案只可能是最大的两个数或者最小的两个数相乘产生，直接维护最大最小次大次小即可。每次可以更新 $[len_{link_k}+1,len_k]$ 的答案，直接线段树。最后遍历一遍线段树输出所有答案。

时间复杂度 $O(n\log n)$。

#include<iostream>
#include<cstdio>
#include<string>
#include<set>
#include<algorithm>
#include<cstring>
using namespace std;
struct edge
{
    int nxt,to;
}e[300001<<1];
int n,tot,h[300001<<1],cnt,link[300001<<1],ch[300001<<1][26],len[300001<<1],lst,s[300001<<2];
long long a[300001],ans[300001<<2][2],tag[300001<<2][2],maxn[300001<<1][2],minn[300001<<1][2];
string str;
inline int ls(int k)
{
    return k<<1;
}
inline int rs(int k)
{
    return k<<1|1;
}
inline void push_up(int k)
{
    ans[k][0]=ans[ls(k)][0]+ans[rs(k)][0];
    ans[k][1]=max(ans[ls(k)][1],ans[rs(k)][1]);
}
inline void push_down(int k,int l,int r)
{
    if(tag[k][0])
    {
        int mid=(l+r)>>1;
        ans[ls(k)][0]+=tag[k][0]*(mid-l+1);
        ans[rs(k)][0]+=tag[k][0]*(r-mid);
        tag[ls(k)][0]+=tag[k][0];
        tag[rs(k)][0]+=tag[k][0];
        tag[k][0]=0;
    }
    if(tag[k][1]!=-1e18-7)
    {
        ans[ls(k)][1]=max(ans[ls(k)][1],tag[k][1]);
        ans[rs(k)][1]=max(ans[rs(k)][1],tag[k][1]);
        tag[ls(k)][1]=max(tag[ls(k)][1],tag[k][1]);
        tag[rs(k)][1]=max(tag[rs(k)][1],tag[k][1]);
        tag[k][1]=-1e18-7;
    }
}
inline void update1(int nl,int nr,int l,int r,int k,long long p)
{
    if(nl>nr)
        return;
    if(l>=nl&&r<=nr)
    {
        ans[k][0]+=(r-l+1)*p;
        tag[k][0]+=p;
        return;
    }
    push_down(k,l,r);
    int mid=(l+r)>>1;
    if(nl<=mid)
        update1(nl,nr,l,mid,ls(k),p);
    if(nr>mid)
        update1(nl,nr,mid+1,r,rs(k),p);
    push_up(k);
}
inline void update2(int nl,int nr,int l,int r,int k,long long p)
{
    if(nl>nr)
        return;
    if(l>=nl&&r<=nr)
    {
        ans[k][1]=max(ans[k][1],p);
        tag[k][1]=max(tag[k][1],p);
        return;
    }
    push_down(k,l,r);
    int mid=(l+r)>>1;
    if(nl<=mid)
        update2(nl,nr,l,mid,ls(k),p);
    if(nr>mid)
        update2(nl,nr,mid+1,r,rs(k),p);
    push_up(k);
}
inline void query(int l,int r,int k)
{
    if(l==r)
    {
        cout<<ans[k][0]<<" "<<(ans[k][0]? ans[k][1]:0)<<'\n';
        return;
    }
    push_down(k,l,r);
    int mid=(l+r)>>1;
    query(l,mid,ls(k));
    query(mid+1,r,rs(k));
}
inline void add(int x,int y)
{
    e[++tot].nxt=h[x];
    h[x]=tot;
    e[tot].to=y;
}
inline void build(int c,int val)
{
    int cur=++cnt,p=lst;
    maxn[cur][0]=minn[cur][0]=val;
    maxn[cur][1]=-1e18;
    minn[cur][1]=1e18;
    s[cur]=1;
    len[cur]=len[lst]+1;
    lst=cur;
    for(;~p;p=link[p])
        if(!ch[p][c])
            ch[p][c]=cur;
        else
            break;
    if(p==-1)
        return;
    int q=ch[p][c];
    if(len[p]+1==len[q])
    {
        link[cur]=q;
        return;
    }
    int clone=++cnt;
    maxn[clone][0]=maxn[clone][1]=-1e18;
    minn[clone][0]=minn[clone][1]=1e18;
    link[clone]=link[q];
    len[clone]=len[p]+1;
    for(int i=0;i<26;++i)
        ch[clone][i]=ch[q][i];
    link[cur]=link[q]=clone;
    for(;~p;p=link[p])
        if(ch[p][c]==q)
            ch[p][c]=clone;
        else
            break;
}
inline void dfs(int k)
{
    for(int i=h[k];i;i=e[i].nxt)
    {
        dfs(e[i].to);
        s[k]+=s[e[i].to];
        if(maxn[e[i].to][0]>maxn[k][0])
        {
            maxn[k][1]=max(maxn[k][0],maxn[e[i].to][1]);
            maxn[k][0]=maxn[e[i].to][0];
        }
        else
            maxn[k][1]=max(maxn[k][1],maxn[e[i].to][0]);
        if(minn[e[i].to][0]<minn[k][0])
        {
            minn[k][1]=min(minn[k][0],minn[e[i].to][1]);
            minn[k][0]=minn[e[i].to][0];
        }
        else
            minn[k][1]=min(minn[k][1],minn[e[i].to][0]);
    }
    if(s[k]>1)
    {
        if(k)
        {
            update1(len[link[k]]+1,len[k],0,n-1,1,1ll*s[k]*(s[k]-1)/2);
            update2(len[link[k]]+1,len[k],0,n-1,1,max(1ll*maxn[k][0]*maxn[k][1],1ll*minn[k][0]*minn[k][1]));
        }
        else
        {
            update1(0,len[k],0,n-1,1,1ll*s[k]*(s[k]-1)/2);
            update2(0,len[k],0,n-1,1,max(1ll*maxn[k][0]*maxn[k][1],1ll*minn[k][0]*minn[k][1]));
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=(n<<2);++i)
        ans[i][1]=tag[i][1]=-1e18-7;
    cin>>str;
    str=" "+str;
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
    link[0]=-1;
    maxn[0][0]=maxn[0][1]=-1e18;
    minn[0][0]=minn[0][1]=1e18;
    for(int i=n;i>=1;--i)
        build(str[i]-'a',a[i]);
    for(int i=1;i<=cnt;++i)
    {
        add(link[i],i);
        //cout<<link[i]<<" "<<i<<endl;
    }
    /*for(int i=0;i<=cnt;++i)
        for(int j=0;j<26;++j)
            if(ch[i][j])
                cout<<i<<" "<<ch[i][j]<<" "<<(char)(j+'a')<<endl;*/
    dfs(0);
    query(0,n-1,1);
    return 0;
}