●BZOJ 3238 [Ahoi2013]差异

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=3238

题解：

后缀数组套路深。

问题转化为求出任意两个后缀的LCP之和

在计算贡献时，各种不爽，
然后就套路的从height[i]数组下手。
计算出 L[i]和 R[i]，
L[i]：找出排名最小(即为 L[i])的后缀与排名为 i的后缀的 LCP==hei[i]
R[i]：找出排名最大(即为 R[i])的后缀与排名为 i的后缀的 LCP==hei[i]
（更直白一点就是在hei数组中找出最大的包含i位置的区间[L,R],使得 hei[i]为区间最小值）
那么呢，这个 hei[i]对答案的贡献即为 2*(i-L[i])*(R[i]-i+1)*hei[i]
意思就是 i 两边的后缀中各任意选出一个，LCP都为 hei[i]。

一个坑点（对于本题（和我的代码实现）而言）
在用单调栈求 L[]和 R[]的时候，
若对于 L[i] 找到第一个小于 hei[i]的位置停下来，
那对于 R[i] 就只能找到第一个小于等于hei[i]位置就停下来，
否则会重复计算。
代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#define MAXN 500050

#define filein(x) freopen(#x".in","r",stdin);

#define fileout(x) freopen(#x".out","w",stdout);

using namespace std;

char S[MAXN];

int sa[MAXN],rak[MAXN],hei[MAXN],L[MAXN],R[MAXN];

long long ANS;

void build(int N,int M){

	static int cc[MAXN],ta[MAXN],tb[MAXN],*x,*y,h,p;

	x=ta; y=tb; h=0;

	for(int i=0;i<M;i++) cc[i]=0;

	for(int i=0;i<N;i++) cc[x[i]=S[i]]++;

	for(int i=1;i<M;i++) cc[i]+=cc[i-1];

	for(int i=N-1;i>=0;i--) sa[--cc[x[i]]]=i;

	for(int k=1;p=0,k<N;k<<=1){

		for(int i=N-k;i<N;i++) y[p++]=i;

		for(int i=0;i<N;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

		for(int i=0;i<M;i++) cc[i]=0;

		for(int i=0;i<N;i++) cc[x[y[i]]]++;

		for(int i=1;i<M;i++) cc[i]+=cc[i-1];

		for(int i=N-1;i>=0;i--) sa[--cc[x[y[i]]]]=y[i];

		swap(x,y); y[N]=-1; x[sa[0]]=0; M=1;

		for(int i=1;i<N;i++)

			x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?M-1:M++;

		if(M>=N) break;

	}

	for(int i=0;i<N;i++) rak[sa[i]]=i;

	for(int i=0,j;i<N;i++){

		if(h) h--;

		if(rak[i]){

			j=sa[rak[i]-1];

			while(S[i+h]==S[j+h]) h++;

		}

		hei[rak[i]]=h;

	}

}

void pre(int N){

	static int stk[MAXN],stp[MAXN],top;

	top=0; stp[top]=0;

	for(int i=0;i<N;i++){

		while(top&&stk[top]>=hei[i]) top--;

		L[i]=stp[top]; top++;

		stk[top]=hei[i]; stp[top]=i;

	}

	top=N; stp[top]=N;

	for(int i=N-1;i>=0;i--){

		while(top<N&&stk[top]>hei[i]) top++;

		R[i]=stp[top]-1; top--;

		stk[top]=hei[i]; stp[top]=i;

	}

	/*for(int i=0;i<N;i++) puts(S+sa[i]);

	printf("\nHeight:\t");

	for(int i=0;i<N;i++) printf("%d ",hei[i]);

	printf("\nL:\t");

	for(int i=0;i<N;i++) printf("%d ",L[i]);

	printf("\nR:\t");

	for(int i=0;i<N;i++) printf("%d ",R[i]);

	printf("\n");*/

}

int main()

{

	scanf("%s",S);

	int N=strlen(S);

	build(N,300);

	pre(N);

	for(int i=N;i;i--) ANS+=1ll*i*(i-1);

	for(int i=N;i;i--) ANS+=1ll*i*(N-i);

//	printf("%lld\n",ANS);

	for(int i=0;i<N;i++)

		ANS-=2ll*(i-L[i])*(R[i]-i+1)*hei[i];

	printf("%lld",ANS);

	return 0;

}

巴特西

●BZOJ 3238 [Ahoi2013]差异

最新文章

热门文章