P2178 [NOI2015] 品酒大会

· · 题解

P2178 [NOI2015] 品酒大会

题意：\forall i\in [0,n) 求有多少对后缀满足len(lcp)\ge i，以及满足条件的两个后缀的权值乘积的最大值。

计算有多少对后缀$(x,y)(x<y)$满足$len(lcp(suf_x,suf_y))=ht_i

因为height[i]=lcp(sa[i],sa[i-1])，也就是说一个ht是反映两个后缀的lcp并且ht_1无意义，所以ht_i控制的后缀范围为[l-1,r]。因为是要满足两个后缀的最小值为ht_i，所以选的两个后缀一定要跨过ht_i，所以x\in [l-1,x-1],y\in[x,r]为，ht_i的贡献为(x-l+1)\times (r-x+1)。

求权值乘积的最大值可以用ST表来维护区间最大值和区间最小值（因为有负数），注意f[i][0]=a[sa[i]]，答案为\max(\min_{i=l-1}^{x-1}a[i]\times min_{i=x}^ra[i],\max_{i=l-1}^{x-1}a[i]\times max_{i=x}^ra[i])。

因为ht_1无意义，所以从ht_2开始，ht_2的左端点为1。

建议认真思考区间边界。

#include<bits/stdc++.h>
#define N 300010
#define ll long long
using namespace std;
inline int read(){
    int w=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=0;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        w=(w<<3)+(w<<1)+(ch^48);
        ch=getchar();
    }
    return f?w:-w;
}
char s[N];
ll res[N],sum[N],f[2][N<<1][25];
int a[N],n,m,sa[N],rk[N],se[N],cnt[N],ht[N],logg[N],stac[N],top,p[N];
inline void qsort(){
    for(int i=0;i<=m;i++) cnt[i]=0;
    for(int i=1;i<=n;i++) cnt[rk[i]]++;
    for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--) sa[cnt[rk[se[i]]]--]=se[i];
}
inline void get_sa(){
    m=122;
    for(int i=1;i<=n;i++) rk[i]=s[i],se[i]=i;
    qsort();
    for(int w=1;w<=n;w<<=1){
        int num=0;
        for(int i=n-w+1;i<=n;i++) se[++num]=i;
        for(int i=1;i<=n;i++) if(sa[i]>w) se[++num]=sa[i]-w;
        qsort();swap(rk,se);rk[sa[1]]=num=1;
        for(int i=2;i<=n;i++) rk[sa[i]]=(se[sa[i]]==se[sa[i-1]]&&se[sa[i]+w]==se[sa[i-1]+w])?num:++num;
        if(num==n)break;m=num;
    }
    for(int i=1,j=0;i<=n;i++){
        if(j)j--;
        while(s[sa[rk[i]]+j]==s[sa[rk[i]-1]+j])j++;
        ht[rk[i]]=j;
    }
}
inline ll askmi(int l,int r){
    int k=logg[r-l+1];
    return min(f[0][l][k],f[0][r-(1<<k)+1][k]);
}
inline ll askma(int l,int r){
    int k=logg[r-l+1];
    return max(f[1][l][k],f[1][r-(1<<k)+1][k]);
}
int main(){
    n=read();scanf("%s",s+1);
    for(int i=1;i<=n;i++) a[i]=read(),res[i]=-2e18;
    //求ht数组
    get_sa();
    //ST表
    for(int i=1;i<=n;i++) f[0][i][0]=f[1][i][0]=a[sa[i]];
    for(int i=2;i<N;i++) logg[i]=logg[i>>1]+1;
    for(int j=1;j<=logg[n];j++)
        for(int i=1;i+(1<<(j-1))-1<=n;i++)
            f[0][i][j]=min(f[0][i][j-1],f[0][i+(1<<(j-1))][j-1]),
            f[1][i][j]=max(f[1][i][j-1],f[1][i+(1<<(j-1))][j-1]);
    //单调栈求贡献区间
    stac[top]=1;//注意不要算ht[1]的贡献
    for(int i=2;i<=n;i++){
        while(top&&ht[stac[top]]>ht[i]){
            int x=stac[top],l=p[x],r=i-1;
            sum[ht[x]]+=1ll*(x-l+1)*(r-x+1);//个数
            if(l<=r) res[ht[x]]=max(res[ht[x]],max(askmi(l-1,x-1)*askmi(x,r),askma(l-1,x-1)*askma(x,r)));//权值最大值
            top--;
        }
        p[i]=stac[top]+1;//左端点
        stac[++top]=i;
    }
    //将栈中元素清空
    while(top){
        int x=stac[top],l=p[x],r=n;//后面没有比它小的，右端点就只能为n
        sum[ht[x]]+=1ll*(x-l+1)*(r-x+1);
        if(l<=r) res[ht[x]]=max(res[ht[x]],max(askmi(l-1,x-1)*askmi(x,r),askma(l-1,x-1)*askma(x,r)));
        top--;
    }
    for(int i=n-1;i>=0;i--) sum[i]+=sum[i+1],res[i]=max(res[i],res[i+1]);//求个后缀和/max
    for(int i=0;i<n;i++) printf("%lld %lld\n",sum[i],res[i]==-2e18?0:res[i]);
    return 0;
}