「BZOJ3238」[Ahoi2013] 差异

2015年4月9日6,1426

Description

Input

一行，一个字符串S

Output

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

Sample Input

cacao

Sample Output

HINT

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

显然后缀数组不是正确姿势。。。

不过还是说说后缀数组的做法吧，bzoj总时限20s是能过的

SA+rmq求lcp应该烂大街了，这题还不用rmq。。。

首先求出h数组

考虑h[i]在哪些区间内会成为最小值，这个用两次单调栈很容易就能解决

还要处理一下由于h[i]可能相同造成的重复计数问题，具体看代码

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 500005
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll ans;
int n,k,p,q=1,top;
int v[N],a[N],h[N],sa[2][N],rk[2][N];
int st[N],l[N],r[N];
char ch[N];
void mul(int *sa,int *rk,int *SA,int *RK)
{
	for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;
	for(int i=n;i;i--)
		if(sa[i]>k)
			SA[v[rk[sa[i]-k]]--]=sa[i]-k;
	for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;
	for(int i=1;i<=n;i++)
		RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]]!=rk[SA[i]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);
}
void presa()
{
	for(int i=1;i<=n;i++)v[a[i]]++;
	for(int i=1;i<=30;i++)v[i]+=v[i-1];
	for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;
	for(int i=1;i<=n;i++)
		rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);
	for(k=1;k<n;k<<=1,swap(p,q))
		mul(sa[p],rk[p],sa[q],rk[q]);
	for(int k=0,i=1;i<=n;i++)
	{
		int j=sa[p][rk[p][i]-1];
		while(ch[j+k]==ch[i+k])k++;
		h[rk[p][i]]=k;if(k>0)k--;		   
	}
}
void solve()
{
	for(int i=1;i<=n;i++)ans+=(ll)i*(n-1);
	h[0]=-inf;
	for(int i=1;i<=n;i++)
	{
		while(h[i]<=h[st[top]])top--;
		if(st[top]==0)l[i]=1;
		else l[i]=st[top]+1;
		st[++top]=i;
	}
	h[n+1]=-inf;top=0;st[0]=n+1;
	for(int i=n;i;i--)
	{
		while(h[i]<h[st[top]])top--;
		if(st[top]==n+1)r[i]=n;
		else r[i]=st[top]-1;
		st[++top]=i;
	}
	for(int i=1;i<=n;i++)
		ans-=2LL*(i-l[i]+1)*(r[i]-i+1)*h[i];
}
int main()
{
	scanf("%s",ch+1);
	n=strlen(ch+1);
	for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1;
	presa();
	solve();
	printf("%lld",ans);
	return 0;
}

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define N 500005

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll ans;

int n,k,p,q=1,top;

int v[N],a[N],h[N],sa[2][N],rk[2][N];

int st[N],l[N],r[N];

char ch[N];

void mul(int *sa,int *rk,int *SA,int *RK)

{

for(int i=1;i<=n;i++)v[rk[sa[i]]]=i;

for(int i=n;i;i--)

if(sa[i]>k)

SA[v[rk[sa[i]-k]]--]=sa[i]-k;

for(int i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;

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

RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]]!=rk[SA[i]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);

}

void presa()

{

for(int i=1;i<=n;i++)v[a[i]]++;

for(int i=1;i<=30;i++)v[i]+=v[i-1];

for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;

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

rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(a[sa[p][i-1]]!=a[sa[p][i]]);

for(k=1;k<n;k<<=1,swap(p,q))

mul(sa[p],rk[p],sa[q],rk[q]);

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

{

int j=sa[p][rk[p][i]-1];

while(ch[j+k]==ch[i+k])k++;

h[rk[p][i]]=k;if(k>0)k--;

}

void solve()

{

for(int i=1;i<=n;i++)ans+=(ll)i*(n-1);

h[0]=-inf;

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

{

while(h[i]<=h[st[top]])top--;

if(st[top]==0)l[i]=1;

else l[i]=st[top]+1;

st[++top]=i;

}

h[n+1]=-inf;top=0;st[0]=n+1;

for(int i=n;i;i--)

{

while(h[i]<h[st[top]])top--;

if(st[top]==n+1)r[i]=n;

else r[i]=st[top]-1;

st[++top]=i;

}

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

ans-=2LL*(i-l[i]+1)*(r[i]-i+1)*h[i];

}

int main()

{

scanf("%s",ch+1);

n=strlen(ch+1);

for(int i=1;i<=n;i++)a[i]=ch[i]-'a'+1;

presa();

solve();

printf("%lld",ans);

return 0;

}

« 「uoj35」后缀排序 [sdoi2008] Sandy的卡片 »

De℃,.: )

跪·什么是正确姿势？

xdj's friend

XDJ！！

ydc

后缀数组为何不是正确姿势

ydc

擦，头像是默认的么，遭不住啊

hzwer

据出题人说是想让大家后缀自动机平衡树什么的。。。。您的id。ydc？

hzwer

您看这数据范围

hzwer.com _ Home | http://hzwer.com

「BZOJ3238」[Ahoi2013] 差异

Description

Input

Output

Sample Input

Sample Output

HINT

分类目录

热门文章

Myfriends

近期评论