【BZOJ3238】[Ahoi2013]差异 后缀数组+单调栈

时间：2021-07-04 12:37:13

【BZOJ3238】[Ahoi2013]差异

Description

【BZOJ3238】[Ahoi2013]差异 后缀数组+单调栈

Input

一行，一个字符串S

Output

一行，一个整数，表示所求值

Sample Input

cacao

Sample Output

54

HINT

2<=N<=500000,S由小写英文字母组成

题解：先跑后缀数组得到height数组，然后我们为了得到∑LCP(i,j)，可以转变成求每个height数组对答案做了多少贡献（也就是有多少对LCP(i,j)=height[i]）。

根据height数组的定义，两个后缀的LCP=height[i]意味着rank[a]和rank[b]中间的所有height都大于等于height[i]，那么我们用两次单调栈处理出height[i]两边第一个比height比i小的数，然后统计一下个数就行了

注意一下height相等的情况，不要重复计算，方法是在两次单调栈中一次用>=，一次用>就行了

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int maxn=500010;

int n,m;

int r[maxn],sa[maxn],ra[maxn],rb[maxn],st[maxn],rank[maxn],h[maxn];

int q[maxn],t,ls[maxn],rs[maxn];

long long ans;

char str[maxn];

void work()

{

	int i,j,k,p,*x=ra,*y=rb;

	for(i=0;i<n;i++)	st[x[i]=r[i]]++;

	for(i=1;i<m;i++)	st[i]+=st[i-1];

	for(i=n-1;i>=0;i--)	sa[--st[x[i]]]=i;

	for(j=p=1;p<n;j<<=1,m=p)

	{

		for(i=n-j,p=0;i<n;i++)	y[p++]=i;

		for(i=0;i<n;i++)	if(sa[i]>=j)	y[p++]=sa[i]-j;

		for(i=0;i<m;i++)	st[i]=0;

		for(i=0;i<n;i++)	st[x[y[i]]]++;

		for(i=1;i<m;i++)	st[i]+=st[i-1];

		for(i=n-1;i>=0;i--)	sa[--st[x[y[i]]]]=y[i];

		for(swap(x,y),i=p=1,x[sa[0]]=0;i<n;i++)

			x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;

	}

	for(i=1;i<n;i++)	rank[sa[i]]=i;

	for(i=k=0;i<n-1;h[rank[i++]]=k)

		for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);

}

int main()

{

	scanf("%s",str),m=27,n=strlen(str);

	int i;

	for(i=0;i<n;i++)	r[i]=str[i]-'a'+1;

	n++,work(),n--;

	h[0]=h[n+1]=-1;

	for(i=1,t=0;i<=n;i++)

	{

		while(t&&h[q[t]]>=h[i])	t--;

		ls[i]=q[t],q[++t]=i;

	}

	for(i=n,t=0,q[0]=n+1;i>=1;i--)

	{

		while(t&&h[q[t]]>h[i])	t--;

		rs[i]=q[t],q[++t]=i;

	}

	ans=(long long)n*(n-1)*(n+1)/2;

	for(i=1;i<=n;i++)	ans-=(long long)h[i]*(i-ls[i])*(rs[i]-i)*2;

	printf("%lld",ans);

	return 0;

}

相关文章