[bzoj4199]-[NOI2015]品酒大会

后缀数组真的很棒……

题目(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("%s",s+1);
	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("%lld %lld\n",ans1[i],ans2[i]);
	return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注