BZOJ3238: [Ahoi2013]差异 后缀数组+单调队列

发现要求的就是每两个后缀之间的LCP之和。顺序并不重要。

那么首先求出后缀数组及其辅助数组rank,height.

我们首先考虑每一个后缀和排名在他之前的后缀的LCP之和（之后的同理）。

假设我们已经知道排名在\(i\)的后缀和其之前的所有后缀的LCP,那么加入当前排名为\(i+1\)的后缀，重新考虑当前的LCP之和，显然只需要维护一个栈顶最大的单调栈即可。

这样我们就可以在\(O(n)\)或者\(O(nlogn)\)内解决这个问题。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

#define N 500010

int v[N],c[N],q[N],nv[N],sa[N],rk[N],h[N];char s[N];
inline bool IsSame(int*v,int a,int b,int hl,int n){
	return v[a]==v[b]&&((a+hl>=n&&b+hl>=n)||(a+hl<n&&b+hl<n&&v[a+hl]==v[b+hl]));
}
inline void GetSa(int*v,int*sa,int n,int m){
	register int i,j,k;
	
	for(i=0;i<m;++i)c[i]=0;
	for(i=0;i<n;++i)++c[v[i]];
	for(i=1;i<m;++i)c[i]+=c[i-1];
	for(i=n-1;i>=0;--i)sa[--c[v[i]]]=i;
	
	for(int d=1;;++d){
		
		//Set in a Queue
		int id=0;int hl=1<<(d-1);
		for(i=0;i<n;++i)if(sa[i]+hl>=n)q[id++]=sa[i];
		for(i=0;i<n;++i)if(sa[i]>=hl)q[id++]=sa[i]-hl;
		
		//Main_Radix_Sort
		for(i=0;i<m;++i)c[i]=0;
		for(i=0;i<n;++i)++c[v[q[i]]];
		for(i=1;i<m;++i)c[i]+=c[i-1];
		for(i=n-1;i>=0;--i)sa[--c[v[q[i]]]]=q[i];
		
		//Relabel
		m=0;
		for(i=0;i<n;++m,i=j+1){
			for(j=i;j<n-1&&IsSame(v,sa[j],sa[j+1],hl,n);++j);
			for(k=i;k<=j;++k)nv[sa[k]]=m;
		}for(i=0;i<n;++i)v[i]=nv[i];
		
		if(m==n)break;
	}
}
void work(int n){
	int i,j;
	for(i=0;i<n;++i)rk[sa[i]]=i;
	for(i=0;i<n;++i){
		if(rk[i]){
			j=0;if(i)j=max(0,h[rk[i-1]]-1);
			while(i+j<n&&sa[rk[i]-1]+j<n&&s[i+j]==s[sa[rk[i]-1]+j])++j;
			h[rk[i]]=j;
		}
	}
}

struct Case{
	LL v,num;
	Case(){}
	Case(LL _v,LL _num):v(_v),num(_num){}
};
Case stack[N];int top;LL nowans,nownum;


int main(){
	#ifndef ONLINE_JUDGE
	//freopen("tt.in","r",stdin);
	//freopen("tt.out","w",stdout);
	#endif

	scanf("%s",s);int len=strlen(s);
	register int i,j;for(i=0;i<len;++i)v[i]=s[i];
	GetSa(v,sa,len,256);
	work(len);

	LL res=0;
	for(i=1;i<=len;++i)res+=(LL)(len-i)*(len-i+1)+(LL)(len-i)*(len-i+1)/2;

	stack[++top]=Case(h[1],1);nowans=h[1];nownum=1;res-=nowans;
	for(i=2;i<len;++i){
		while(top&&h[i]<=stack[top].v)nowans-=(LL)stack[top].v*stack[top].num,nownum-=stack[top--].num;
		stack[++top]=Case(h[i],i-nownum);nownum=i;nowans+=(LL)stack[top].v*stack[top].num;
		res-=nowans;
	}

	top=0;stack[++top]=Case(h[len-1],1);nowans=h[len-1];nownum=1;res-=nowans;
	for(i=len-3;i>=0;--i){
		while(top&&h[i+1]<=stack[top].v)nowans-=(LL)stack[top].v*stack[top].num,nownum-=stack[top--].num;
		stack[++top]=Case(h[i+1],len-1-i-nownum),nownum=len-1-i,nowans+=(LL)stack[top].v*stack[top].num;
		res-=nowans;
	}

	printf("%lld\n",res);return 0;
}