[BZOJ]4199: [Noi2015]品酒大会(后缀数组+笛卡尔树)

时间:2022-09-19 08:55:55

Time Limit: 10 Sec  Memory Limit: 512 MB

Description

[BZOJ]4199: [Noi2015]品酒大会(后缀数组+笛卡尔树)

Input

[BZOJ]4199: [Noi2015]品酒大会(后缀数组+笛卡尔树)

Output

[BZOJ]4199: [Noi2015]品酒大会(后缀数组+笛卡尔树)

Sample Input

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7

Sample Output

45 56
10 56
3 32
0 0
0 0
0 0
0 0
0 0
0 0
0 0

HINT

[BZOJ]4199: [Noi2015]品酒大会(后缀数组+笛卡尔树)

[BZOJ]4199: [Noi2015]品酒大会(后缀数组+笛卡尔树)

Solution

  先求出后缀数组,两个后缀的最长公共前缀是它们之间height的最小值,对height建笛卡尔树,树上维护最大最小值即可。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
inline int read()
{
int x,f=;char c;
while((c=getchar())<''||c>'')if(c=='-')f=;
for(x=c-'';(c=getchar())>=''&&c<='';)x=x*+c-'';
return f?x:-x;
}
#define MN 300000
int v[MN+],ar[MN*+],*sa=ar,*nsa=sa+MN+,*rk=nsa+MN+,*nrk=rk+MN+,h[MN+];
int a[MN+],z[MN+],zn,lc[MN+],rc[MN+],sz[MN+],mx[MN+],mn[MN+];
ll f1[MN+],f2[MN+];
char s[MN+];
void dfs(int x)
{
if(!x)return;
int l=lc[x],r=rc[x];
dfs(l);dfs(r);
if(!l)l=MN+,sz[l]=,mx[l]=mn[l]=a[sa[x-]];
if(!r)r=MN+,sz[r]=,mx[r]=mn[r]=a[sa[x]];
f1[h[x]]+=1LL*sz[l]*sz[r];
f2[h[x]]=max(f2[h[x]],max(max(1LL*mn[l]*mn[r],1LL*mn[l]*mx[r]),
max(1LL*mx[l]*mn[r],1LL*mx[l]*mx[r])));
sz[x]=sz[l]+sz[r];
mn[x]=min(mn[l],mn[r]);
mx[x]=max(mx[l],mx[r]);
}
int main()
{
int n=read(),l,i,x;
scanf("%s",s+);
for(i=;i<=n;++i)a[i]=read();
for(i=;i<=n;++i)++v[s[i]];
for(i='a';i<='z';++i)v[i]+=v[i-];
for(i=;i<=n;++i)sa[v[s[i]]--]=i;
for(i=;i<=n;++i)rk[sa[i]]=rk[sa[i-]]+(s[sa[i]]!=s[sa[i-]]);
for(l=;l<n;l<<=,swap(sa,nsa),swap(rk,nrk))
{
for(i=;i<=n;++i)v[rk[sa[i]]]=i;
for(i=n;i;--i)if(sa[i]>l)nsa[v[rk[sa[i]-l]]--]=sa[i]-l;
for(i=;i<l;++i)nsa[v[rk[n-i]]--]=n-i;
for(i=;i<=n;++i)nrk[nsa[i]]=nrk[nsa[i-]]+(rk[nsa[i]]!=rk[nsa[i-]]||rk[nsa[i]+l]!=rk[nsa[i-]+l]);
}
for(i=,l=;i<=n;++i,l?--l:)
if(rk[i]>){for(x=sa[rk[i]-];s[i+l]==s[x+l];++l);h[rk[i]]=l;}
for(i=;i<=n;++i)
{
while(zn&&h[i]<h[z[zn]])lc[i]=z[zn--];
rc[z[zn]]=i;z[++zn]=i;
}
memset(f2,,sizeof(f2));
dfs(z[]);
for(i=n;i--;)f1[i]+=f1[i+],f2[i]=max(f2[i],f2[i+]);
for(i=;i<n;++i)printf("%lld %lld\n",f1[i],f1[i]?f2[i]:);
}