BZOJ 2119: 股市的预测

Description

求形如ABA形式的字符串，其中B长度固定，\(n\leqslant 10^5\)

Solution

后缀数组。

我们可以枚举一个长度\(x\)，然后将序列分组，每组长度为\(x\)，然后从\(i\)找和\(i+x+B\)的最长公共后缀和最长公共前缀，然后得到一组合法区间，限制一下在块中防止重复即可。

复杂度就是调和级数。

复杂度\(O(nlogn)\)

Code

/**************************************************************Problem: 2119User: BeiYuLanguage: C++Result: AcceptedTime:1680 msMemory:14972 kb
****************************************************************/#include 
using namespace std;const int N = 100050;
const int M = 25;inline int in(int x=0,char ch=getchar()) { while(ch>'9'||ch<'0') ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x; }int l,n,m,B;
long long ans;
int a[N],b[N];namespace SA {int t1[N],t2[N],c[N],sa[N],rk[N],ht[N];int pw2[N],lg2[N];int st[N][M];void get_sa(int a[],int n=::n,int m=::m) {int *x=t1,*y=t2;for(int i=1;i<=m;i++) c[i]=0;for(int i=1;i<=n;i++) c[x[i]=a[i]]++;for(int i=1;i<=m;i++) c[i]+=c[i-1];for(int i=n;i;--i) sa[c[x[i]]--]=i;for(int k=1,p=0;kk) y[++p]=sa[i]-k;for(int i=1;i<=m;i++) c[i]=0;for(int i=1;i<=n;i++) c[x[i]]++;for(int i=1;i<=m;i++) c[i]+=c[i-1];for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i];swap(x,y),x[sa[1]]=p=1;for(int i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;if(p>=n) break;m=p;}}void get_ht(int a[],int n=::n) {for(int i=1;i<=n;i++) rk[sa[i]]=i;for(int i=1,j,k=0;i<=n;ht[rk[i++]]=k)for(j=sa[rk[i]-1],k=k?k-1:k;a[i+k]==a[j+k];k++);}void get_st(int n=::n) {pw2[0]=1;for(int i=1;i>1]+1;for(int i=1;i<=n;i++) st[i][0]=ht[i];for(int j=1;jy) swap(x,y);x++;int lg=lg2[y-x+1];return min(st[x][lg],st[y-pw2[lg]+1][lg]);}
}
using namespace SA;void Solve(int x) {
//  cout<<"x:"<"<=x) ans+=r+l-x+1;}
}
int main() {l=n=in(),B=in();for(int i=1;i<=n;i++) b[i]=in();for(int i=1;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！