LibreOJ 2133 「NOI2015」品酒大会

相似其实就是两个后缀的公共前缀。
根据题意可以对于两个后缀只算 LCP 的贡献，最后做一下后缀和与后缀最大值。

两个后缀的 LCP 就是后缀树上的 LCA，所以可以对于每个结点统计以它为 LCA 的贡献。
第一问计数比较简单。
第二问最大乘积，由于有负数，所以答案可能是最大值与次大值或最小值与次小值之积。
稍微维护一下即可。

以及注意特判一下大小不到 2 不可能有贡献的子树。

所以这题用后缀树来做就超水对吧……

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e5;
int n,a[N + 5];
char s[N + 5];
int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v;
    pre[tot] = first[u];
    first[u] = tot;
}
int sz[(N << 1) + 5],mx[(N << 1) + 5],mx1[(N << 1) + 5],mn[(N << 1) + 5],mn1[(N << 1) + 5];
long long sum[N + 5],ans[N + 5];
struct node
{
    int ch[26];
    int fa,len;
} sam[(N << 1) + 5];
int whole = 1,tot = 1;
void insert(int x,int w)
{
    int cur = whole,p = whole = ++tot;
    sam[p].len = sam[cur].len + 1,sz[p] = 1,mx[p] = mn[p] = w;
    for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
        sam[cur].ch[x] = p;
    if(!cur)
        sam[p].fa = 1;
    else
    {
        int q = sam[cur].ch[x];
        if(sam[cur].len + 1 == sam[q].len)
            sam[p].fa = q;
        else
        {
            int nxt = ++tot;
            sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
            for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                sam[cur].ch[x] = nxt;
        }
    }
}
void dfs(int p)
{
    int SZ = sz[p];
    for(register int i = first[p];i;i = pre[i])
    {
        dfs(to[i]),SZ += sz[to[i]];
        if(mx[p] < mx[to[i]])
            mx1[p] = max(mx[p],mx1[to[i]]),mx[p] = mx[to[i]];
        else
            mx1[p] = max(mx1[p],mx[to[i]]);
        if(mn[p] > mn[to[i]])
            mn1[p] = min(mn[p],mn1[to[i]]),mn[p] = mn[to[i]];
        else
            mn1[p] = min(mn1[p],mn[to[i]]);
    }
    if(SZ < 2)
        return ;
    ans[sam[p].len] = max(ans[sam[p].len],max((long long)mx[p] * mx1[p],(long long)mn[p] * mn1[p]));
    for(register int i = first[p];i;i = pre[i])
        sum[sam[p].len] += (long long)sz[p] * sz[to[i]],sz[p] += sz[to[i]];
}
int main()
{
    scanf("%d%s",&n,s + 1);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    memset(mx,-0x3f,sizeof mx),memset(mx1,-0x3f,sizeof mx1),memset(mn,0x3f,sizeof mn),memset(mn1,0x3f,sizeof mn1),memset(ans,-0x3f,sizeof ans);
    for(register int i = n;i;--i)
        insert(s[i] - 'a',a[i]);
    for(register int i = 1;i <= tot;++i)
        add(sam[i].fa,i);
    dfs(1);
    for(register int i = n - 1;~i;--i)
        sum[i] += sum[i + 1],ans[i] = max(ans[i],ans[i + 1]);
    for(register int i = 0;i < n;++i)
        printf("%lld %lld\n",sum[i],!sum[i] ? 0 : ans[i]);
}