【[SDOI2016]生成魔咒】

这是一道\(SA\)的练手好题

建议做之前先去做一下2408

之后你就肯定会做这道题了

首先上面那道题的答案就是

\[\sum_{i=1}^nn+1-sa[i]-het[i]
\]

就是对于每一个后缀求出其能产生的子串，之后减掉和之前本质相同的子串

对于这个题，我们需要求出所有前缀的本质不同的子串个数

先无脑敲上\(sa\)和\(het\)的板子，之后我们只需要往里面动态添加后缀就好了

但是如果正着处理的话会有一个非常显然的问题，也就是我们加进去一个后缀，但是这个后缀和之前的一些后缀形成的\(lcp\)长度超过当前的长度，会导致我们很难计算

所以我们需要把字符串倒过来，之后每次往里面添加一个后缀就只相当于往里面添加了一个字符

反置字符串显然不会令子串变得不相等，于是我们可以完美解决这个问题

之后我们维护上面的那个柿子就好了，由于我们插入的\(sa\)值并不连续，所以我们不能直接用\(het\)，而是\(het\)的最小值

于是我们用一个\(st\)表来查询\(het\)的最小值，之后每插入一个点相当于要断裂一个原来存在的排名连续的后缀，所以还需要一个\(set\)来找前驱和后继

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<set>

#define re register

#define LL long long

#define maxn 100005

#define set_it std::set<int>::iterator

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	re char c=getchar();int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

int a[maxn],rk[maxn],tp[maxn],tax[maxn],sa[maxn],het[maxn],b[maxn],to[maxn];

int St[maxn][18],log_2[maxn];

int n,m,sz;LL ans=1;

std::set<int> s;

inline void qsort()

{

	for(re int i=0;i<=m;i++) tax[i]=0;

	for(re int i=1;i<=n;i++) tax[rk[i]]++;

	for(re int i=1;i<=m;i++) tax[i]+=tax[i-1];

	for(re int i=n;i;--i) sa[tax[rk[tp[i]]]--]=tp[i];

}

inline int Pre(int x)

{

    s.insert(x); set_it i=s.find(x);

    if(i==s.begin()) return -1; --i; return *i;

}

inline int Nxt(int x) {set_it i=s.find(x);++i;if(i==s.end()) return -1;return *i;}

inline int find(int x)

{

	int l=1,r=sz;while(l<=r)

	{

		int mid=l+r>>1;if(b[mid]==x) return mid;

		if(b[mid]<x) l=mid+1;else r=mid-1;

	}return 0;

}

inline int ask(int l,int r) {int k=log_2[r-l+1];return min(St[l][k],St[r-(1<<k)+1][k]);}

int main()

{

	n=read();for(re int i=n;i;--i) a[i]=read(),b[i]=a[i];

	std::sort(b+1,b+n+1);m=sz=std::unique(b+1,b+n+1)-b-1;

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

	for(re int i=1;i<=n;i++) rk[i]=a[i],tp[i]=i;

	qsort();

	for(re int w=1,p=0;p<n;w<<=1,m=p)

	{

		p=0;

		for(re int i=1;i<=w;i++) tp[++p]=n-w+i;

		for(re int i=1;i<=n;i++) if(sa[i]>w) tp[++p]=sa[i]-w;

		qsort();for(re int i=1;i<=n;i++) std::swap(rk[i],tp[i]);

		rk[sa[1]]=p=1;

		for(re int i=2;i<=n;i++) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;

	}

	int k=0;

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

	{

		if(k) --k;

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

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

		het[rk[i]]=k;

	}

	for(re int i=2;i<=n;i++) log_2[i]=1+log_2[i>>1];

	for(re int i=1;i<=n;i++) St[i][0]=het[i];

	for(re int j=1;j<=17;j++)

		for(re int i=1;i+(1<<j)-1<=n;i++)

			St[i][j]=min(St[i][j-1],St[i+(1<<(j-1))][j-1]);puts("1");s.insert(rk[n]);

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

	{

		ans+=n-i+1;

		int x=Pre(rk[i]);

		if(x!=-1) {int t=ask(x+1,rk[i]);ans+=to[x],ans-=t;to[x]=t;}

		x=Nxt(rk[i]);

		if(x!=-1) to[rk[i]]=ask(rk[i]+1,x),ans-=to[rk[i]];

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

	}

	return 0;

}

巴特西

【[SDOI2016]生成魔咒】

最新文章

热门文章