bzoj千题计划312：bzoj2119: 股市的预测（后缀数组+st表）

https://www.lydsy.com/JudgeOnline/problem.php?id=2119

题意：将给定数组差分后，求ABA形式的字串个数，要求|B|=m，|A|>0

1、后缀数组求出 差分序列 和 翻转差分序列后的序列 的sa，rk，height

2、枚举len=|A|，对差分序列每len个分一块，记每一块的关键点位块内第一个元素

3、枚举每一个关键点i，令j=i+len+m，求出若i作为A的最后一个元素，向左能延伸最远点x，若i作为A的第一个元素，向右能延伸的最远点y

　 那么i取[x,y]内的任意长为len的一块都可以最为A，所以答案累加 y-x+1 - len +1

4、为避免重复，限制向左向右最长延伸长度为len-1，即每个A只能占据一个关键点

5、向左能延伸的最远点就是 分别以i、j结尾的最长公共后缀，即求[1,i]和[1,j]的最长公共后缀，转化成求翻转序列的最长公共前缀

      向右能延伸的最远点就是 分别以i、j开始的最长公共前缀，即求[i,n]和[j,n]的最长公共前缀

      这可以用后缀数组完成

#include
#include
#include
#include
#includeusing namespace std;#define N 50001
#define M 15typedef long long LL;int n,m,tot;
int b[N];int a1[N],a2[N];int has[N];int sa1[2][N],rk1[2][N],h1[N];
int sa2[2][N],rk2[2][N],h2[N];int p1,q1=1;
int p2,q2=1;
int v[N];
int k;int st1[N][M+1],st2[N][M+1];void read(int &x)
{x=0; int f=1; char c=getchar();while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }x*=f;
}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]]!=rk[SA[i-1]] || rk[SA[i]+k]!=rk[SA[i-1]+k]);
}void presa(int &p,int &q,int a[N],int sa[2][N],int rk[2][N])
{memset(v,0,sizeof(v));for(int i=1;i<=n;++i) v[a[i]]++;for(int i=1;i<=tot;++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]]!=a[sa[p][i-1]]);for(k=1;k1,swap(p,q)) mul(sa[p],rk[p],sa[q],rk[q]);
}void get_height(int *a,int *h,int *sa,int *rk)
{int k=0,j;for(int i=1;i<=n;++i){j=sa[rk[i]-1];while(a[i+k]==a[j+k]) k++;h[rk[i]]=k;if(k) k--;}
}void prest(int h[N],int st[N][M+1])
{for(int i=2;i<=n;++i) st[i][0]=h[i];for(int i=1,k=2;i<=M;++i,k<<=1)for(int j=2;j+k-1<=n;++j)st[j][i]=min(st[j][i-1],st[j+k/2][i-1]);
}int get(int st[N][M+1],int i,int j,int *rk)
{i=rk[i]; j=rk[j];if(i>j) swap(i,j);i++;int l=1.0*log(j-i+1)/log(2);return min(st[i][l],st[j-(1<1][l]);
}void solve()
{LL ans=0;int j;int lcp,lcs,sum;for(int len=1;lenlen)for(int i=1;i+len+m<=n;i+=len){j=i+len+m;lcs=get(st1,i,j,rk1[p1]);if(lcs>len) lcs=len;lcp=get(st2,n-j+1,n-i+1,rk2[p2]);if(lcp>len) lcp=len;sum=lcp+lcs-1;if(sum>=len) {ans+=sum-len+1;//    printf("%d %d %d %d\n",i,j,len,sum-len+1);
            }}cout<<ans;
}int main()
{freopen("nt2011_stock.in","r",stdin);freopen("nt2011_stock.out","w",stdout); read(n); read(m);for(int i=1;i<=n;++i) read(b[i]);for(int i=1;i1]-b[i],has[i]=a1[i];n--;sort(has+1,has+n+1);tot=unique(has+1,has+n+1)-has-1;for(int i=1;i<=n;++i) a1[i]=lower_bound(has+1,has+tot+1,a1[i])-has;for(int i=1;i<=n;++i) a2[n-i+1]=a1[i];presa(p1,q1,a1,sa1,rk1);get_height(a1,h1,sa1[p1],rk1[p1]);presa(p2,q2,a2,sa2,rk2);get_height(a2,h2,sa2[p2],rk2[p2]);prest(h1,st1);prest(h2,st2);solve();
}

转载于:https://www.cnblogs.com/TheRoadToTheGold/p/8976953.html

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