??题目传送门：loj#2133 luoguP2178
??简要题意：给定一个字符串\(s\)，每个后缀都有权值，对于每个长度\(len\)，求出所有最长公共前缀\(\geq len\)的后缀对的总数和每个这样的后缀对，两后缀权值乘积的最大值。
??我们可以先把后缀数组求出来，把最长公共前缀长度转化为height数组的区间\(\min\)，考虑固定\(len\)，容易发现合法的后缀对的取值范围被height数组上小于\(len\)的位置划分成了若干区间，同时当\(len\)变小的时候，相邻区间会发生合并。
??于是倒序枚举\(len\)，用并查集辅助合并合法区间，同时统计贡献就可以解决问题了。
my code
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 300010
inline ll read()
{
ll x=0; char c=getchar(),f=1;
for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
return x*f;
}
inline void write(ll x)
{
static char buf[20];
int len=0;
if(x<0)putchar('-'),x=-x;
for(;x;x/=10)buf[len++]=x%10+'0';
if(!len)putchar('0');
else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
int sa[maxn],rk[maxn],lcp[maxn];
int a[maxn],fa[maxn],l[maxn],r[maxn],mx1[maxn],mx2[maxn],mn1[maxn],mn2[maxn],id[maxn];
ll cnt[maxn],mx[maxn];
char s[maxn];
int n;
ll tot,cur;
void getsa(char* s,int n)
{
int cnt=256;
static int tsa[maxn],trk[maxn],sum[maxn];
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
trk[i]=s[i]+1,++sum[trk[i]];
for(int i=1;i<=cnt;i++)
sum[i]+=sum[i-1];
for(int i=n;i;i--)
sa[sum[trk[i]]--]=i;
cnt=1; rk[sa[1]]=1;
for(int i=2;i<=n;i++){
if(trk[sa[i]]!=trk[sa[i-1]])++cnt;
rk[sa[i]]=cnt;
}
for(int len=1;cnt<n;len<<=1){
int tot=0;
for(int i=n-len+1;i<=n;i++)
tsa[++tot]=i;
for(int i=1;i<=n;i++)
if(sa[i]>len)tsa[++tot]=sa[i]-len;
memset(sum,0,sizeof(sum));
memcpy(trk,rk,sizeof(rk));
for(int i=1;i<=n;i++)
++sum[trk[tsa[i]]];
for(int i=1;i<=cnt;i++)
sum[i]+=sum[i-1];
for(int i=n;i;i--)
sa[sum[trk[tsa[i]]]--]=tsa[i];
cnt=1; rk[sa[1]]=1;
for(int i=2;i<=n;i++){
if(trk[sa[i]]!=trk[sa[i-1]]||trk[sa[i]+len]!=trk[sa[i-1]+len])++cnt;
rk[sa[i]]=cnt;
}
}
for(int i=1;i<=n;i++)
if(rk[i]>1){
lcp[rk[i]]=std::max(lcp[rk[i-1]]-1,0);
while(s[i+lcp[rk[i]]]==s[sa[rk[i]-1]+lcp[rk[i]]])++lcp[rk[i]];
}
}
bool cmp(int x,int y){return lcp[x]>lcp[y];}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void modify(int now)
{
int p1=find(now-1),p2=find(now);
fa[p1]=p2;
tot-=(ll)(r[p1]-l[p1]+1)*(r[p1]-l[p1])/2+(ll)(r[p2]-l[p2]+1)*(r[p2]-l[p2])/2;
l[p2]=l[p1];
if(mx1[p1]>mx1[p2]){
int t1=mx1[p1],t2=std::max(mx1[p2],mx2[p1]);
mx1[p2]=t1; mx2[p2]=t2;
}
else{
int t1=mx1[p2],t2=std::max(mx1[p1],mx2[p2]);
mx1[p2]=t1; mx2[p2]=t2;
}
if(mn1[p1]<mn1[p2]){
int t1=mn1[p1],t2=std::min(mn1[p2],mn2[p1]);
mn1[p2]=t1; mn2[p2]=t2;
}
else{
int t1=mn1[p2],t2=std::min(mn1[p1],mn2[p2]);
mn2[p2]=t1; mn2[p2]=t2;
}
tot+=(ll)(r[p2]-l[p2]+1)*(r[p2]-l[p2])/2;
cur=std::max(cur,std::max((ll)mx1[p2]*mx2[p2],(ll)mn1[p2]*mn2[p2]));
}
int main()
{
n=read();
scanf("%s",s+1);
getsa(s,n);
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=2;i<=n;i++)
id[i]=i;
std::sort(id+2,id+n+1,cmp);
tot=0; cur=-1ll<<60;
for(int i=1;i<=n;i++){
fa[i]=i;
l[i]=r[i]=i;
mx1[i]=a[sa[i]]; mx2[i]=-inf;
mn1[i]=a[sa[i]]; mn2[i]=inf;
}
int now=2;
for(int i=n-1;i>=0;i--){
while(now<=n&&lcp[id[now]]>=i)modify(id[now++]);
cnt[i]=tot; mx[i]=cur;
}
for(int i=0;i<n;i++)
if(cnt[i])writesp(cnt[i]),writeln(mx[i]);
else puts("0 0");
return 0;
}【loj#2133 && luoguP2178】[NOI2015]品酒大会
原文：https://www.cnblogs.com/quzhizhou/p/11997922.html