本文共 3419 字，大约阅读时间需要 11 分钟。

$T1$

第$p$杯酒和第$q$杯酒的最大相似度就是$LCP(suffix(p),suffix(q))$

然后我们需要知道有多少$height$区间的最小值大于等于$r$

设区间是$[L,R]$的$height$区间合法,说明$suffix(L-1)$和$suffix(R)$的$LCP$满足条件

显然这个可以枚举每个$sa[i]$作为左端点,用$st$表加二分确定最大右端点$x$来解决

得到满足条件的最大右端点$x$之后,求最大美味值也好求,我们只需要知道$[s{a}_{i+1},s{a}_x]$的最大美味值即可

这个可以再次用$ST$表预处理,或者直接上线段树

但是题目是求$r\in [0,n-1]$的所有答案

我们的算法求单次答案的复杂度为$O(nlog(n))$,显然无法通过,拿到$40$分

$T2$

其实上面的思路是非常蠢的,我们只需要枚举左端点和右端点,求出$height$的区间最小值$x$

然后去更新相似度为$x$的方案书和最大值,最后从前往后方案累加,最大值取$max$就好了

复杂度$O(n^2)$

$T3$

仍然是枚举相似度$x$

那么$height$数组区间的最小值大于等于$x$的区间都是合法的

我们把$height$区间分成若干个这样的连续合法区间,每个区间的方案数很好算,任取两个端点即可

最大值呢?也好办,就是动态维护这个区间的最大,次大,最小,次小即可

$T4$

观察到上面的瓶颈主要是枚举相似度

那我们能不能不枚举相似度呢??

可以,我们只对严格相似度为$x$的区间计算方案和最大值,那么最后从后往前累计方案,最大值取$max$即可

某段$height$区间的最大相似度取决于最小值，所以我们从大到小动态插入$height[i]$

也就是使用并查集每次合并$sa[i-1]$和$sa[i]$

并查集维护的每个元素就是$height$的某一段区间，保存这段区间的元素个数

最大值,最小值，次大值，次小值，用来算最大贡献

#include 
   
    using namespace std;#define int long longconst int maxn = 3e5+10;int n,m,a[maxn];char b[maxn];int sa[maxn],x[maxn],y[maxn],rk[maxn],height[maxn],c[maxn];void SA(char a[]){
   	m = 500;	for(int i=1;i<=n;i++)	c[x[i]=a[i]]++;	for(int i=1;i<=m;i++)	c[i] += c[i-1];	for(int i=n;i>=1;i--)	sa[c[x[i]]--] = i;	for(int k=1;k<=n;k<<=1)	{
   		int num = 0;		for(int i=n-k+1;i<=n;i++)	y[++num] = i;		for(int i=1;i<=n;i++)	if( sa[i]>k )	y[++num] = sa[i]-k;		for(int i=0;i<=m;i++)	c[i] = 0;		for(int i=1;i<=n;i++)	c[x[i]]++;		for(int i=1;i<=m;i++)	c[i] += c[i-1];		for(int i=n;i>=1;i--)	sa[c[x[y[i]]]--] = y[i], y[i] = 0;		swap(x,y);		num = 1, x[sa[1]] = 1;		for(int i=2;i<=n;i++)			x[sa[i]] = ( y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k] )?num:++num;		if( num==n )	break;		m = num;	}	for(int i=1;i<=n;i++)	rk[sa[i]] = i;	for(int i=1,k=0;i<=n;i++)	{
   		if( rk[i]==1 )	continue;		if( k )	k--; int j = sa[rk[i]-1];		while( i+k<=n&&j+k<=n&&a[i+k]==a[j+k] )	k++;		height[rk[i]] = k;	}}int pre[maxn],mi[maxn],mx[maxn],id[maxn],ans[maxn],ans1[maxn],ans2[maxn],siz[maxn];bool com(int a,int b){
    return height[a]>height[b]; }int find(int x){
    return x==pre[x]?x:pre[x]=find( pre[x] ); }void merge(int x,int y,int len){
   	x = find(x), y = find(y);	pre[y] = x;//现在x才是祖先	ans1[len] += siz[x]*siz[y];	siz[x] += siz[y]; 	ans[x] = max( ans[x],ans[y] );	ans[x] = max( ans[x],max(mx[x]*mi[y],mx[x]*mx[y]) );	ans[x] = max( ans[x],max(mi[x]*mi[y],mi[x]*mx[y]) );	mx[x] = max( mx[x],mx[y] );	mi[x] = min( mi[x],mi[y] );	ans2[len] = max( ans2[len],ans[x] );}signed main(){
   	cin >> n >> ( b+1 );	for(int i=1;i<=n;i++)	cin >> a[i];	SA(b);	for(int i=1;i<=n;i++)		pre[i] = id[i] = i, mx[i] = mi[i] = a[i], siz[i] = 1, ans[i] = -1e18;	sort( id+2,id+1+n,com );	memset( ans2,-0x3f,sizeof ans2 );	for(int i=2;i<=n;i++)		merge( sa[id[i]],sa[id[i]-1],height[id[i]] );//从大到小加入height[i] 	for(int i=n;i>=0;i--)	ans1[i] += ans1[i+1];	for(int i=n;i>=0;i--)	ans2[i] = max( ans2[i],ans2[i+1] );	for(int i=0;i
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114438446 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！