题目（BZOJ）
题目（LibreOJ）
题目（洛谷）
这题其实很好做
根据r相似的定义，我们很容易想到这是俩后缀的LCP，所以只需要建个后缀数组就可以了。
题目中的r相似包含r-1到0相似，所以当找到p和q是r相似时，我们就往下处理。
根据预处理的height数组，我们开一个vector，然后按height值从大到小进行处理。
这个处理可以用并查集解决，只需要合并时维护max，min（美味度可能为负），cnt（集合大小），就可以一次性将两个问题处理完了。
（.,.....然而这题我表示一眼过去就是SAM，然而不会写233）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
e=0;int ck=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ck=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
e*=ck;
}
const int N=300050;
int n,b[N],f[N];ll cnt[N],mx[N],mn[N],ans1[N],ans2[N];
char s[N];
vector <int> g[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline int idx(char c){return c-'a'+1;}
struct Suffix_Array{
int p,q,k,a[N],v[N],h[N],sa[2][N],rk[2][N];
inline void mulsa(int *sa,int *rk,int *SA,int *RK){
for(int i=1;i<=n;++i)v[rk[sa[i]]]=i;
for(int i=n;i;--i)if(sa[i]>k)SA[v[rk[sa[i]-k]]--]=sa[i]-k;
for(int i=n-k+1;i<=n;++i)SA[v[rk[i]]--]=i;
for(int i=1;i<=n;++i)RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
}
inline void initsa(){
for(int i=1;i<=n;++i)v[a[i]]++;
for(int i=1;i<=30;++i)v[i]+=v[i-1];
for(int i=1;i<=n;++i)sa[p][v[a[i]]--]=i;
for(int i=1;i<=n;++i)rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);
for(k=1;k<n;k<<=1,swap(p,q))mulsa(sa[p],rk[p],sa[q],rk[q]);
for(int i=1,k=0;i<=n;++i){
int j=sa[p][rk[p][i]-1];
while(a[i+k]==a[j+k])++k;
h[rk[p][i]]=k;if(k>0)--k;
}
}
inline void data_clear(){
memset(rk,0,sizeof rk);
memset(sa,0,sizeof sa);
memset(v,0,sizeof v);
memset(h,0,sizeof h);
memset(a,0,sizeof a);
p=k=0,q=1;
}
}A;
ll tot,tmp;
inline void comb(int x,int y){
int px=find(x),py=find(y);
if(px==py)return;
if(px>py)swap(px,py);
f[py]=px;
ll tt=max(mx[px]*mx[py],mn[px]*mn[py]);
if(!tot||tt>tmp)tmp=tt;
tot+=cnt[px]*cnt[py];
mx[px]=max(mx[px],mx[py]);
mn[px]=min(mn[px],mn[py]);
cnt[px]+=cnt[py];
}
int main(){
A.data_clear();
read(n);
scanf(
for(int i=1;i<=n;++i)read(b[i]);
for(int i=1;i<=n;++i)A.a[i]=idx(s[i]);
A.initsa();
for(int i=1;i<=n;++i)f[i]=i;
for(int i=1;i<=n;++i)mn[i]=mx[i]=b[A.sa[A.p][i]],cnt[i]=1;
for(int i=2;i<=n;++i)g[A.h[i]].push_back(i);
for(int k=n-1;k>=0;--k){
for(int i=0;i<g[k].size();++i){
int v=g[k][i];
comb(v,v-1);
}
ans1[k]=tot;ans2[k]=tmp;
}
for(int i=0;i<n;++i)printf(
return 0;
}
Comments NOTHING