以前一直听说什么后缀数组height合并之类的
表示我这种后缀数组都敲不熟的蒟蒻怎么会写
但是做了做觉得还是很简单的嘛
这个题是有两问的，第一问是求LCP>=R的后缀对有多少个
这个就是AHOI2013 差异 稍微变个形啦
直接逆序建后缀自动机，在parent树上做一个很简单的树P就可以了
因为对于现在parent树而言，任意两点的LCP等于两点在树上的LCA的len
到这里，其实我们已经可以拿到70分了
一部分数据暴力，一部分数据LCP<10也可以暴力，还有一部分数据ai相等，等价于只用求第一问
之后我们考虑第二问，对于当前的parent树而言，等价于求parent树上两个叶节点乘积的最大值
又因为考虑到ai可能是负数，所以我们只需要记录最大值，次大值，最小值，次小值就可以了
这也是一个非常简单的树P
UPD：题目可以去UOJ去看
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std; typedef long long LL;
const int maxn=600010;
const LL oo=1LL<<62;
int n,cnt,la;
int a[maxn];
char s[maxn];
struct Node{
int next[26];
int len,link;
}st[maxn];
int t[maxn],b[maxn];
LL ans1[maxn],ans2[maxn];
LL mx[maxn],cmx[maxn];
LL mn[maxn],cmn[maxn];
LL sum[maxn]; void read(int &num){
num=0;int f=1;char ch=getchar();
while(ch<'!')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
num*=f;
}
void init(){
cnt=la=0;
st[0].link=-1;
}
void add(int c){
int cur=++cnt;
st[cur].len=st[la].len+1;
int p;
for(p=la;p!=-1&&st[p].next[c]==0;p=st[p].link)st[p].next[c]=cur;
if(p==-1)st[cur].link=0;
else{
int q=st[p].next[c];
if(st[q].len==st[p].len+1)st[cur].link=q;
else{
int clone=++cnt;
st[clone]=st[q];
st[clone].len=st[p].len+1;
for(;p!=-1&&st[p].next[c]==q;p=st[p].link)st[p].next[c]=clone;
st[cur].link=st[q].link=clone;
}
}la=cur;
} int main(){
read(n);scanf("%s",s+1);init();
for(int i=1;i<=n;++i)read(a[i]);
for(int i=n;i>=1;--i)add(s[i]-'a');
for(int i=0;i<=cnt;++i){
mx[i]=-oo;cmx[i]=-oo;
mn[i]=oo;cmn[i]=oo;
}
int now=0;
for(int i=n;i>=1;--i){
int id=s[i]-'a';
now=st[now].next[id];
sum[now]++;
mx[now]=a[i];mn[now]=a[i];
}
for(int i=0;i<=cnt;++i)t[st[i].len]++;
for(int i=1;i<=n;++i)t[i]+=t[i-1];
for(int i=0;i<=cnt;++i)b[--t[st[i].len]]=i;
for(int i=0;i<=n;++i)ans2[i]=-oo;
for(int i=cnt;i>=0;--i){
int v=b[i],u=st[v].link,R=st[v].len,L=st[u].len; LL tmp=-oo;
if(cmx[v]!=-oo)tmp=max(tmp,mx[v]*cmx[v]);
if(cmn[v]!=oo)tmp=max(tmp,mn[v]*cmn[v]);
if(tmp!=-oo)ans2[R]=max(ans2[R],tmp); ans1[L]+=sum[u]*sum[v]; sum[u]=sum[u]+sum[v]; if(mx[v]>=mx[u]){cmx[u]=mx[u];mx[u]=mx[v];}
else if(mx[v]>cmx[u])cmx[u]=mx[v]; if(mn[v]<=mn[u]){cmn[u]=mn[u];mn[u]=mn[v];}
else if(mn[v]<cmn[u])cmn[u]=mn[v];
}
for(int i=n-1;i>=0;--i)ans1[i]+=ans1[i+1];
for(int i=n-1;i>=0;--i)ans2[i]=max(ans2[i],ans2[i+1]);
for(int i=0;i<n;++i){
if(!ans1[i])ans2[i]=0;
printf("%lld %lld\n",ans1[i],ans2[i]);
}return 0;
}