BZOJ4516: [Sdoi2016]生成魔咒

果然SA比SAM+map快。

首先这是SAM裸题，然而SA求本质不同子串个数也很容易。考虑倒着建SA，这样没错加一个字符就变成加一个后缀，其他后缀都不变，那么i的答案就是只考虑前i个后缀的答案。搞个双向链表，每次删一个后缀并RMQ更新答案。

（SAM+map复杂度可能是错的，但是我不清楚）

#include<algorithm>
#include<cstdio>
#define lb lower_bound
using namespace std;
const int N=1e5+5;
typedef int arr[N];
arr sa,r,f[17],c,v,s,t,p,q;
typedef long long ll;
ll b,z[N];
void pre(int*s,int n){
	for(int i=0;i<n;++i)
		++c[s[i]];
	for(int i=1;i<n;++i)
		c[i]+=c[i-1];
	for(int i=n-1;~i;--i)
		sa[--c[s[i]]]=i;
	int m=0;
	for(int i=1;i<n;++i)
		r[sa[i]]=s[sa[i]]!=s[sa[i-1]]?++m:m;
	for(int j=1;;j<<=1){
		if(++m==n)break;
		for(int i=0;i<j;++i)
			v[i]=n-j+i;
		for(int i=0;i<m;++i)
			c[i]=0;
		for(int i=0,k=j;i<n;++i){
			if(sa[i]>=j)
				v[k++]=sa[i]-j;
			++c[r[i]];
		}
		for(int i=1;i<m;++i)
			c[i]+=c[i-1];
		for(int i=n-1;~i;--i)
			sa[--c[r[v[i]]]]=v[i],v[i]=r[i];
		m=r[sa[0]]=0;
		for(int i=1;i<n;++i)
			r[sa[i]]=v[sa[i]]!=v[sa[i-1]]||v[sa[i]+j]!=v[sa[i-1]+j]?++m:m;
	}
}
int ask(int i,int j){
	int k=__lg(j-i+1);
	return min(f[k][i],f[k][j-(1<<k)+1]);
}
struct buf{
	char z[9<<17],*s;
	buf():s(z){
		z[fread(z,1,sizeof z,stdin)]=0;
	}
	operator int(){
		int x=0;
		while(*s<48)++s;
		while(*s>32)
			x=x*10+*s++-48;
		return x;
	}
}it;
int main(){
	int n=it;
	for(int i=n-1;~i;--i)
		s[i]=t[i]=it;
	sort(t,t+n);
	for(int i=0;i<n;++i)
		s[i]=lb(t,t+n,s[i])-t+1;
	pre(s,n+1);
	for(int i=0,j=0;i<n;++i){
		if(j)--j;
		while(s[i+j]==s[sa[r[i]-1]+j])++j;
		f[0][r[i]]=j;
	}
	for(int j=1;n>>j;++j)
		for(int i=0;i+(1<<j)-1<=n;++i)
			f[j][i]=min(f[j-1][i],f[j-1][i+(1<<j-1)]);
	for(int i=1;i<=n;++i)
		b+=n-sa[i]-f[0][i];
	for(int i=n;i>1;--i)
		p[i]=i-1;
	for(int i=1;i<n;++i)
		q[i]=i+1;
	for(int i=0;i<n;++i){
		int j=r[i],k=0;
		if(p[j])k=max(k,ask(p[j]+1,j));
		if(q[j])k=max(k,ask(j+1,q[j]));
		z[i]=b,b-=n-i-k;
		p[q[j]]=p[j];
		q[p[j]]=q[j];
	}
	for(int i=n-1;~i;--i)
		printf("%lld
",z[i]);
}

BZOJ4516: [Sdoi2016]生成魔咒

相关推荐