洛谷 P-2178 品酒大会(后缀自动机)

品酒大会

又一道黑题！以为自己 $O (n)$ 的算法常数过大才TLE的，因此最终代码加了一堆优化（不过现在把register全给删了，不然有点难看），2333
后面发现得加差分以及后缀思想才是 $O (n)$ 。。。不过也好，跑起来速度挺快的。

题意：有一个字符串，字符串第i个位置有权值a[i]，求出所有r相似方案数以及r相似的最大美味值，美味值定义为a[i]*a[j]，其中i，j为r相似(相似的具体定义见下方题干)

思路：

由于r相似定义为长度为r的相同子串，且有用的权值为两个字符串的首位置，因此倒过来建后缀自动机就可以利用endpos
然后正常的求出每个节点的endpos数目(cnt)
由于每一个节点对r相似方案的贡献从r=len到r=minlen都是相同的，都为 $c n t * (c n t - 1) / 2$ ，也就是从endpos中任选两个的方案数，同时此处利用差分可以加速
再来求r相似的最大美味值，由于一个节点的最大美味值可以对len相似到0相似都产生相同的效果，因此只需要记录对len相似的贡献，然后利用后缀思想即可
但求r相似的最大美味值也不容易，毕竟a[i]有正有负；这里我们可以先维护每个节点endpos权值的前两大以及前两小，然后就可以求出每个节点的最大美味值啦
最后的最后就是一些小细节，比如longlong，最大美味值的初始化之类的。

题目描述

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-')c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int ch[maxn][26], fa[maxn], len[maxn], cnt[maxn], endpos[maxn];
int last=1, sz=1, n;
ll maxs[maxn][2], mins[maxn][2];
int a[maxn];
ll node[maxn], cntr[maxn], ans[maxn];

int id[maxn], c[maxn];

void add(int c, int pos) {
    int p=last, np=last=++sz;
    len[np]=len[p]+1, endpos[np]=pos, cnt[np]=1; //注意记录endpos
    for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++sz;
            fa[nq]=fa[q], len[nq]=len[p]+1;
            memcpy(ch[nq],ch[q],104);
            fa[q]=fa[np]=nq;
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

int main() {
    //ios::sync_with_stdio(false);
    n=read();
    for(int i=0; i<=2*n; ++i) maxs[i][0]=maxs[i][1]=-2e9, mins[i][0]=mins[i][1]=2e9;
    for(int i=0; i<=2*n; ++i) node[i]=-1e18;
    for(int i=0; i<n; ++i) ans[i]=-1e18;
    scanf("%s", s);
    reverse(s,s+n);
    for(int i=0; i<n; ++i) add(s[i]-'a',i+1);
    for(int i=1; i<=n; ++i) a[i]=read();
    reverse(a+1,a+1+n);
    
    for(int i=2; i<=sz; ++i) if(cnt[i]) maxs[i][0]=mins[i][0]=a[endpos[i]]; //必须是有cnt的点才进行初始化更新
    for(int i=1; i<=sz; ++i) c[len[i]]++;
    for(int i=1; i<=sz; ++i) c[i]+=c[i-1];
    for(int i=1; i<=sz; ++i) id[c[len[i]]--]=i;
    for(int i=sz; i; --i) cnt[fa[id[i]]]+=cnt[id[i]]; //计数排序求每个节点endpos数目
    for(int i=1; i<=sz; ++i) {
        cntr[len[i]]+=1LL*cnt[i]*(cnt[i]-1)/2;
        if(fa[i]) cntr[len[fa[i]]]-=1LL*cnt[i]*(cnt[i]-1)/2; //差分加速
    }
    for(int i=n-2; i>=0; --i) cntr[i]+=cntr[i+1];

    for(int i=sz; i; --i) { //维护前两大以及前两小
        int p=fa[id[i]];
        ll mx0=maxs[id[i]][0], mx1=maxs[id[i]][1];
        ll mi0=mins[id[i]][0], mi1=mins[id[i]][1];
        if(mx1>=maxs[p][0]) swap(maxs[p][0],maxs[p][1]), maxs[p][0]=mx1;
        else if(mx1>maxs[p][1]) maxs[p][1]=mx1;
        if(mx0>=maxs[p][0]) swap(maxs[p][0],maxs[p][1]), maxs[p][0]=mx0;
        else if(mx0>maxs[p][1]) maxs[p][1]=mx0;
        if(mi1<=mins[p][0]) swap(mins[p][0],mins[p][1]), mins[p][0]=mi1;
        else if(mi1<mins[p][1]) mins[p][1]=mi1;
        if(mi0<=mins[p][0]) swap(mins[p][0],mins[p][1]), mins[p][0]=mi0;
        else if(mi0<mins[p][1]) mins[p][1]=mi0;
    }
    for(int i=1; i<=sz; ++i) { //维护好以后就可以更新每个节点的最大美味值了
        if(maxs[i][1]!=-2e9) node[i]=max(node[i],maxs[i][0]*maxs[i][1]);
        if(mins[i][1]!=2e9) node[i]=max(node[i],mins[i][0]*mins[i][1]);
    }

    for(int i=1; i<=sz; ++i) ans[len[i]]=max(ans[len[i]],node[i]); //后缀思想更新答案最大美味值第一步
    ll m=-1e18;
    for(int i=n-1; i>=0; --i) m=max(m,ans[i]), ans[i]=m; //第二步
    for(int i=0; i<n; ++i) if(ans[i]==-1e18) ans[i]=0; //一开始初始化的-1e18，现在改回来

    for(int i=0; i<n; ++i) printf("%lld %lld\n", cntr[i], ans[i]);
}