题解 P2178 【[NOI2015]品酒大会】

· · 题解

思路:后缀数组＋单调栈

我们先计算严格k相似的两瓶酒的答案，所谓严格k相似，就是以这两瓶酒对应的后缀开头（注解：字面意思，一个后缀的开头位置），它们的最长前缀长度正好是k。然后输出答案前从后往前把方案数累计一下，把最大值取max一下即可。

首先后缀数组和Height都处理出来，然后我们知道，对于排名为i和j的两个后缀(i<j)，它们的lcp就是Height_i到Height_j之间的最小值

我们按照排名从小到大开始处理。

这个单调栈不是一般的单调栈，里面存的一个元素不是一个后缀开头，而是一个按照排名连续的后缀开头区间。并且我们要顺路维护：

st：区间末尾Height值，即如果该区间后面的一个后缀开头要和该区间里任何一个元素搭配，酒都是st相似的。这也是单调栈中要单调的东西。

sz:区间元素个数

mx:区间最大值

mi:区间最小值

既要维护最大值又要维护最小值，是因为负负得正，两个负数的乘积可能是最大值。

然后按排名从大到小处理时，对于后缀开头i,如果Height_{i+1}小于st(top)，说明再往后的后缀开头和i及栈顶区间的后缀开头搭配的时候，酒不再是st(top)相似的，而变成了Height_{i+1}相似的了。所以我们计算i与栈顶区间元素搭配的贡献，再将i和栈顶区间合并，栈顶弹出。对于新的栈顶，以此类推......

最后，我们对于还留在栈里的若干区间，从后往前用相似的方法处理一边即可。

具体处理方法有点讲不清楚，看代码work函数吧。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=0,w=1;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q*w;
}
#define RI register int
typedef long long LL;
const int N=300005,inf=0x3f3f3f3f;
int n,m;
int v[N],a[N],x[N],y[N],T[N],SA[N],Hei[N];
char s[N];
void Rsort() {
    for(RI i=0;i<=m;++i) T[i]=0;
    for(RI i=1;i<=n;++i) ++T[x[y[i]]];
    for(RI i=1;i<=m;++i) T[i]+=T[i-1];
    for(RI i=n;i>=1;--i) SA[T[x[y[i]]]--]=y[i];
}
int cmp(RI i,RI j,RI num) {return y[i]==y[j]&&y[i+num]==y[j+num];}
void getSA() {
    for(RI i=1;i<=n;++i) a[i]=s[i-1]-'a'+1,x[i]=a[i],y[i]=i;
    m=26,Rsort();
    for(RI km=1,num=1;km<n;num+=num,m=km) {
        km=0;
        for(RI i=n-num+1;i<=n;++i) y[++km]=i;
        for(RI i=1;i<=n;++i) if(SA[i]>num) y[++km]=SA[i]-num;
        Rsort(),swap(x,y),x[SA[1]]=km=1;
        for(RI i=2;i<=n;++i) x[SA[i]]=cmp(SA[i],SA[i-1],num)?km:++km;
    }
}
void getHei() {
    RI lcp=0;
    for(RI i=1;i<=n;++i) {
        if(lcp) --lcp;
        RI j=SA[x[i]-1];
        while(i+lcp<=n&&j+lcp<=n&&a[i+lcp]==a[j+lcp]) ++lcp;
        Hei[x[i]]=lcp;
    }
}
LL ans1[N],ans2[N];int sz[N],mx[N],mi[N],st[N],top;
void work() {
    RI ksz,kmx,kmi;
    for(RI i=1;i<=n;++i) ans2[i]=LLONG_MIN;
    for(RI i=2;i<=n;++i) {
        ksz=1,kmx=kmi=v[SA[i-1]];
        while(top&&st[top]>=Hei[i]) {
            ans1[st[top]]+=1LL*sz[top]*ksz;//方案贡献
            ans2[st[top]]=max(ans2[st[top]],max(1LL*mx[top]*kmx,1LL*mi[top]*kmi));//最大值贡献
            ksz+=sz[top],kmx=max(kmx,mx[top]),kmi=min(kmi,mi[top]);//合并
            --top;
        }
        ++top,st[top]=Hei[i],sz[top]=ksz,mi[top]=kmi,mx[top]=kmx;
    }
    ksz=1,kmx=kmi=v[SA[n]];
    for(RI i=top;i>=1;--i) {
        ans1[st[i]]+=1LL*sz[i]*ksz;//方案贡献
        ans2[st[i]]=max(ans2[st[i]],max(1LL*mx[i]*kmx,1LL*mi[i]*kmi));//最大值贡献
        ksz+=sz[i],kmx=max(kmx,mx[i]),kmi=min(kmi,mi[i]);//合并
    }
}
int main()
{
    n=read(),scanf("%s",s);
    for(RI i=1;i<=n;++i) v[i]=read();
    getSA(),getHei(),work();
    for(RI i=n-2;i>=0;--i) ans1[i]+=ans1[i+1],ans2[i]=max(ans2[i],ans2[i+1]);
    for(RI i=0;i<n;++i)
        printf("%lld %lld\n",ans1[i],(ans1[i]==0?0:ans2[i]));
    return 0;
}