NKOJ 4000 （AHOI 2013）差异（后缀自动机/后缀数组+线段树/单调队列）

发表于 |
字数统计: 1,472字 | 阅读时长 ≈ 8min

P4000 [Ahoi2013]差异

问题描述

这里写图片描述

输入格式

一行，一个字符串S

输出格式

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

样例输入

cacao

样例输出

54

提示

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

还是先说优美的自动机做法，将字符串反过来建立后缀自动机，那么后缀的前缀变成前缀的后缀，那么变成在后缀自动机parent树上求LCA

考虑到所有的LCP要求和，那么考虑每一个节点会多少次被当做LCA，显然如果统计出每颗子树Right集合的大小，即子树表示了多少个前缀，那么两两子树的前缀数相乘求和就是当前点被当做LCA的次数。因为不同子树中的点的LCA一定是当前节点。

然后还要考虑选择了子树中的一个点和当前点的情况，此时需要注意到统计Right集合时，复制出来的点并不代表一次新的出现位置，因此只有当当前点不是复制的点时，才加上每个子树的前缀数。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
char s[N];
long long Ans;
int n,m,tot=1,las=1,rt=1,Max[N],pra[N],son[N][27],v[N];
int TOT,LA[N],NE[N],EN[N];
int NP(int x)
{
	Max[++tot]=x;
	return tot;
}
void Ins(int t)
{
	int p=las,q,np,nq;
	np=NP(Max[p]+1);v[np]=1;
	while(p&&!son[p][t])son[p][t]=np,p=pra[p];
	if(!p)pra[np]=rt;
	else
	{
		q=son[p][t];
		if(Max[q]==Max[p]+1)pra[np]=q;
		else 
		{
			nq=NP(Max[p]+1);
			memcpy(son[nq],son[q],sizeof(son[q]));
			pra[nq]=pra[q];
			pra[q]=pra[np]=nq;
			while(son[p][t]==q)son[p][t]=nq,p=pra[p];
		}
	}
	las=np;
}
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int x)
{
	int i,y;long long tmp=0,tt=v[x];
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];DFS(y);
		v[x]+=v[y];
		tmp+=1ll*v[y]*tt;
		tt+=v[y];
	}
	Ans+=1ll*tmp*Max[x];
}
int main()
{
	int i,j;
	scanf("%s",s);
	n=strlen(s);
	for(i=0;i<n;i++)Ins(s[i]-'a');
	for(i=1;i<=tot;i++)ADD(pra[i],i);
	DFS(rt);printf("%lld",1ll*n*(n+1)/2*(n-1)-Ans*2);
}

然后是略微麻烦的后缀数组做法。
优秀的思路是考虑每一个Height有多少次被作为LCP加入答案，那么显然需要找到左右第一个小于他的位置。用单调队列/栈即可。但是需要注意由于Height相同而产生的重复计算。

一个更粗暴的想法是直接用线段树维护当前的已经求出的LCP值，每次讨论一个新的Height时，把大于他的LCP值变成当前的Height，然后新加入一个Height，然后对整颗线段树求和累加到答案上即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
#define N 555555
using namespace std;
char s[N];
int n,SA[N],H[N],Rank[N];
int wa[N],wb[N],T[N];
int tot,ls[N*4],rs[N*4],lazy[N*4],cnt[N*4];
ll sum[N*4];
bool cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void GSA(char *r,int *sa,int a,int b)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<a;i++)T[x[i]=r[i]]++;
	for(i=1;i<b;i++)T[i]+=T[i-1];
	for(i=a-1;i>=0;i--)sa[--T[x[i]]]=i;
	for(p=1,j=1;p<a;j<<=1,b=p)
	{
		for(p=0,i=a-j;i<a;i++)y[p++]=i;
		for(i=0;i<a;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<b;i++)T[i]=0;
		for(i=0;i<a;i++)T[x[y[i]]]++;
		for(i=1;i<b;i++)T[i]+=T[i-1];
		for(i=a-1;i>=0;i--)sa[--T[x[y[i]]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<a;i++)
		x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void GH(char *r,int *sa,int a)
{
	int i,j,k=0;
	for(i=1;i<=a;i++)Rank[sa[i]]=i;
	for(i=0;i<a;H[Rank[i++]]=k)
	for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
void PD(int p)
{
	lazy[ls[p]]=lazy[rs[p]]=1;lazy[p]=0;
	sum[ls[p]]=sum[rs[p]]=cnt[ls[p]]=cnt[rs[p]]=0;
}
int BT(int x,int y)
{
	int p=++tot;
	if(x<y)
	{
		int mid=x+y>>1;
		ls[p]=BT(x,mid);
		rs[p]=BT(mid+1,y);
	}
	return p;
}
void ADD(int p,int l,int r,int k,int d)
{
	if(lazy[p])PD(p);
	if(l==r){cnt[p]+=d;sum[p]=1ll*cnt[p]*l;return;}
	int mid=l+r>>1;
	if(k<=mid)ADD(ls[p],l,mid,k,d);
	else ADD(rs[p],mid+1,r,k,d);
	cnt[p]=cnt[ls[p]]+cnt[rs[p]];
	sum[p]=sum[ls[p]]+sum[rs[p]];
}
int GC(int p,int l,int r,int x,int y)
{
	if(lazy[p])return 0;
	if(x<=l&&y>=r)
	{
		int k=cnt[p];
		cnt[p]=sum[p]=0;
		lazy[p]=1;
		return k;
	}
	int mid=l+r>>1,cs=0;
	if(x<=mid&&y>=l)cs+=GC(ls[p],l,mid,x,y);
	if(x<=r&&y>mid)cs+=GC(rs[p],mid+1,r,x,y);
	cnt[p]=cnt[ls[p]]+cnt[rs[p]];
	sum[p]=sum[ls[p]]+sum[rs[p]];
	return cs;
}
void GA()
{
	int i,k;ll ans=0;
	BT(1,n);H[n+1]=H[n]+1;
	for(i=n-1;i>0;i--)
	{
		if(H[i+1]<H[i+2])k=GC(1,1,n,H[i+1]+1,H[i+2]);
		else k=0;
		if(H[i+1])ADD(1,1,n,H[i+1],k+1);
		ans+=sum[1];
	}
	printf("%lld",1ll*n*(1ll*n+1ll)/2ll*(1ll*n-1ll)-ans*2);
}
int main()
{
	scanf("%s",s);
	n=strlen(s);s[n]='a'-1;
	GSA(s,SA,n+1,300);
	GH(s,SA,n);GA();
}