P2178 [NOI2015] 品酒大会

· · 个人记录

前言，听wjd哥哥说这题SA挺好写，所以我写SAM。

把图片上传也墙了就离谱

这题自主想出来还是不难的（只要1h）。

\text{Solution}

相似:例如

1 2 3 4 5

a b c b a

其中，下标为2的b与下标为4的b是1相似。

我们发现，这也就是bcba与ba的反过来之后的LCP。（不难想，我想了大概半小时）

发现就是后缀的前缀，建SAM然后建后缀树跑LCP。

对于权值乘积最大，可以记录最大、次大、最小、次小。

然后可以求出每一个r相似，然后再从 [n-1,0] 这样更新。

然后有个树形dp求有序点对方案的要注意下。

\text{Code}

#include <bits/stdc++.h>

#define N (int)(1e6+5)
#define int long long
#define inf (int)(2e18)

using namespace std;

struct edge {
    int nex,to;
}e[N];

char s[N];
int head[N],cnt,a[N],fa[N],len[N],son[26][N],sz[N],mx[N],mx2[N],mi[N],mi2[N];
int n,las=1,tot=1;

void ins(int c,int v) {
    int pre=las,x=++tot; las=x; len[x]=len[pre]+1; mx[x]=v; mx2[x]=-inf; mi[x]=v; mi2[x]=inf; sz[x]=1;
    for(;pre&&!son[c][pre];pre=fa[pre]) son[c][pre]=x;
    int y=son[c][pre];
    if(!pre) fa[x]=1;
    else if(len[y]==len[pre]+1) fa[x]=y;
    else {
        int p=++tot; len[p]=len[pre]+1;
        fa[p]=fa[y]; fa[x]=fa[y]=p;
        for(int i=0;i<26;i++) son[i][p]=son[i][y];
        for(;pre&&son[c][pre]==y;pre=fa[pre]) son[c][pre]=p; 
    }
}

int ans[N],sum[N];
void dfs(int x) {
    int nsz=0;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        dfs(y);
    //  if(len[x]==1) {
        if(mx[y]>=mx[x]) {
            mx2[x]=max(mx2[y],mx[x]); mx[x]=mx[y];
        } else if(mx[y]>mx2[x]) mx2[x]=mx[y];
    //  }
        if(mi[y]<=mi[x]) {
            mi2[x]=min(mi2[y],mi[x]); mi[x]=mi[y];
        } else if(mi[y]<mi2[x]) mi2[x]=mi[y];

        nsz+=sz[y];
    }
    if(nsz+sz[x]<2) return;
/*  if(len[x]==1) {
        cout<<sz[x]<<" "<<mx[x]<<" "<<mx2[x]<<endl;
        ans=max(ans,mx[x]*mx2[x]);
        //ans+=pre_sz*(sz[x]-pre_sz);
    }
*/  
    ans[len[x]]=max(ans[len[x]],mx[x]*mx2[x]);
    ans[len[x]]=max(ans[len[x]],mi[x]*mi2[x]);
//  cout<<len[x]<<" "<<mx[x]<<" "<<mx2[x]<<" "<<mi[x]<<" "<<mi2[x]<<endl;
    for(int i=head[x];i;i=e[i].nex) {
        int y=e[i].to;
        sum[len[x]]+=sz[x]*sz[y]; sz[x]+=sz[y]; //能保证是有序点对，即不会算2次。 
    }
}

void add_edge(int x,int y) {
    e[++cnt].nex=head[x]; e[cnt].to=y;
    head[x]=cnt;
}

void init() {
    for(int i=0;i<N;i++) {
        mx[i]=mx2[i]=-inf; mi[i]=mi2[i]=inf;
    } 
}

signed main() {
//  freopen("P1278_1.in","r",stdin);
    init();
    scanf("%d%s",&n,s+1); //n=strlen(s+1);// cout<<n<<endl;
    for(int i=0;i<=n+1;i++) ans[i]=-inf;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=n;i>=1;i--) ins(s[i]-'a',a[i]);
    for(int i=2;i<=tot;i++) add_edge(fa[i],i);
    dfs(1);
    for(int i=n;i>=0;i--) sum[i]+=sum[i+1],ans[i]=max(ans[i],ans[i+1]);
    for(int i=0;i<n;i++) printf("%lld %lld\n",sum[i],!sum[i]?0:ans[i]);
    return 0;
}