题解 P2178 【[NOI2015]品酒大会】
devout
2020-12-11 15:51:41
对于两个以 $i,j$ 开头的后缀，显然他会对 $0\sim LCP(i,j)$ 的相似度的答案有贡献
所以考虑先用 SA 求出 $height$ 数组
因为 $LCP(i,j)=\min\{height_k\},k\in(i,j]$，所以对于每一个 $height_i$，我们找到左右第一个 $height$ 不小于他的位置，设为 $l,r$，那么对于每一个 $p\in(l,i),q\in[i,r),LCP(p,q)=height_i$
我们可以用单调栈得到这个区间，然后利用组合数学和ST表就可以求出 $LCP$ 的位置上的答案了，然后做一下后缀和/后缀max
注意这里会出现一个问题，如果他左边/右边第一个不小于他的位置刚好等于他，那么这个时候会出现问题（如样例1）
所以我们每次找左边第一个小于他的，和右边第一个小于等于他的，就可以做到不重不漏的计算了
```cpp
# include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(register int i=a;i<=b;i++)
# define _Rep(i,a,b) for(register int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=3e5+5;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,m;
char s[N];
int a[N];
ll ans1[N];
ll ans2[N];
int stk[N],top;
int sa[N],rk[N],dy[N],sum[N];
int L[N],R[N];
int height[N];
int mx[N][20],mi[N][20],lg[N];
void RadixSort(){
Rep(i,1,m)sum[i]=0;
Rep(i,1,n)sum[rk[i]]++;
Rep(i,1,m)sum[i]+=sum[i-1];
_Rep(i,n,1)sa[sum[rk[dy[i]]]--]=dy[i];
}
void SA(){
m='z';
Rep(i,1,n)rk[i]=s[i],dy[i]=i;
RadixSort();
for(int k=1,t=0;t<n;k<<=1,m=t){
t=0;
_Rep(i,n,n-k+1)dy[++t]=i;
Rep(i,1,n)if(sa[i]>k)dy[++t]=sa[i]-k;
RadixSort();
swap(rk,dy);
rk[sa[1]]=t=1;
Rep(i,2,n)
rk[sa[i]]=dy[sa[i]]==dy[sa[i-1]]&&(sa[i]+k<=n&&sa[i-1]+k<=n&&dy[sa[i]+k]==dy[sa[i-1]+k])?t:++t;
}
Rep(i,1,n)rk[sa[i]]=i;
int k=0;
Rep(i,1,n){
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
height[rk[i]]=k;
}
}
void init(){
memset(mx,-0x3f,sizeof(mx));
memset(mi,0x3f,sizeof(mi));
lg[1]=0;
Rep(i,2,n)lg[i]=lg[i>>1]+1;
_Rep(i,n,1){
mx[i][0]=mi[i][0]=a[sa[i]];
Rep(j,1,19){
if(i+(1<<j-1)>n)break;
mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
}
}
}
int getmax(int i,int j){
int k=lg[j-i+1];
return max(mx[i][k],mx[j-(1<<k)+1][k]);
}
int getmin(int i,int j){
int k=lg[j-i+1];
return min(mi[i][k],mi[j-(1<<k)+1][k]);
}
int main()
{
memset(ans2,-0x3f,sizeof(ans2));
read(n);
scanf("%s",s+1);
Rep(i,1,n)read(a[i]);
SA();
Rep(i,2,n){
while(top&&height[stk[top]]>=height[i])top--;
L[i]=top?stk[top]:1;
stk[++top]=i;
}
top=0;
_Rep(i,n,2){
while(top&&height[stk[top]]>height[i])top--;
R[i]=top?stk[top]:n+1;
stk[++top]=i;
}
Rep(i,2,n)ans1[height[i]]+=1ll*(i-L[i])*(R[i]-i);
_Rep(i,n,0)ans1[i]+=ans1[i+1];
init();
Rep(i,2,n)
ans2[height[i]]=max(ans2[height[i]],max(1ll*getmax(L[i],i-1)*getmax(i,R[i]-1),1ll*getmin(L[i],i-1)*getmin(i,R[i]-1)));
_Rep(i,n,0)ans2[i]=max(ans2[i],ans2[i+1]);
Rep(i,0,n-1)printf("%lld %lld\n",ans1[i],ans1[i]?ans2[i]:ans1[i]);
return 0;
}
```