【bzoj4516】 Sdoi2016—生成魔咒

时间：2024-01-10 20:30:44

http://www.lydsy.com/JudgeOnline/problem.php?id=4516 (题目链接)

题意

　　依次向字符串末尾加上一个字符，每次求不同子串个数。

Solution

　　如果不是字符的范围太大，这道题就是个板子题。。所以我们把后缀自动机上的边用map存下就好了。

　　伦说hash可以做，但是这hash挂链不是很慢吗。。 、

　　原来可以邻接表，我是sb。。。

细节

　　SAM数组开两倍。

代码

// bzoj4516

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

int n,Dargen,last,sz;

int par[maxn<<1],len[maxn<<1];

LL ans;

map<int,int> ch[maxn<<1];

void Extend(int c) {

	int np=++sz,p=last;last=np;

	len[np]=len[p]+1;

	for (;p && !ch[p][c];p=par[p]) ch[p][c]=np;

	if (!p) par[np]=Dargen;

	else {

		int q=ch[p][c];

		if (len[p]+1==len[q]) par[np]=q;

		else {

			int nq=++sz;len[nq]=len[p]+1;

			ch[nq]=ch[q];

			par[nq]=par[q];

			par[np]=par[q]=nq;

			for (;p && ch[p][c]==q;p=par[p]) ch[p][c]=nq;

		}

	}

	ans+=len[np]-len[par[np]];

	printf("%lld\n",ans);

}

int main() {

	scanf("%d",&n);

	Dargen=last=sz=1;

	for (int x,i=1;i<=n;i++) {

		scanf("%d",&x);

		Extend(x);

	}

	return 0;

}

Solution

　　后缀数组+双向链表。左转题解：http://blog.csdn.net/clove_unique/article/details/53911757

代码

// bzoj4516

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100010;

int sa[maxn],rank[maxn],height[maxn];

int s[maxn],t[maxn],nxt[maxn],pre[maxn],ans[maxn];

int n;

namespace Suffix {

	int wa[maxn],wb[maxn],ww[maxn];

	bool cmp(int *r,int a,int b,int l) {

		return r[a]==r[b] && r[a+l]==r[b+l];

	}

	void da(int *r,int *sa,int n,int m) {

		int i,j,p,*x=wa,*y=wb;

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

		for (i=1;i<=n;i++) ww[x[i]=r[i]]++;

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

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

		for (p=0,j=1;p<n;j*=2,m=p) {

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

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

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

			for (i=1;i<=n;i++) ww[x[y[i]]]++;

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

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

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

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

		}

	}

	void calheight(int *r,int *sa,int n) {

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

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

			if (k) k--;

			int j=sa[rank[i]-1];

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

			height[rank[i]]=k;

		}

	}

}

using namespace Suffix;

int main() {

	scanf("%d",&n);

	for (int i=1;i<=n;i++) scanf("%d",&s[i]),t[i]=s[i];

	for (int i=1;i<=n>>1;i++) swap(s[i],s[n-i+1]);

	sort(t+1,t+1+n);

	int tmp=unique(t+1,t+1+n)-t-1;

	for (int i=1;i<=n;i++) s[i]=lower_bound(t+1,t+1+tmp,s[i])-t;

	da(s,sa,n,tmp);

	calheight(s,sa,n);

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

		nxt[i]=i+1;

		pre[i]=i-1;

	}

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

		int k=rank[i];

		ans[i]=n-i+1-max(height[k],height[nxt[k]]);

		height[nxt[k]]=min(height[nxt[k]],height[k]);

		nxt[pre[k]]=nxt[k];

		pre[nxt[k]]=pre[k];

	}

	LL res=0;

	for (int i=n;i>=1;i--) {

		res+=ans[i];

		printf("%lld\n",res);

	}

	return 0;

}

相关文章