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<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 50001

#define M 15

typedef long long LL;

int n,m,tot;

int b[N];

int a1[N],a2[N];

int has[N];

int sa1[][N],rk1[][N],h1[N];

int sa2[][N],rk2[][N],h2[N];

int p1,q1=;

int p2,q2=;

int v[N];

int k;

int st1[N][M+],st2[N][M+];

void read(int &x)

{

    x=; int f=; char c=getchar();

    while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

    x*=f;

}

void mul(int *sa,int *rk,int*SA,int *RK)

{

    for(int i=;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+;i<=n;++i) SA[v[rk[i]]--]=i;

    for(int i=;i<=n;++i) RK[SA[i]]=RK[SA[i-]]+(rk[SA[i]]!=rk[SA[i-]] || rk[SA[i]+k]!=rk[SA[i-]+k]);

}

void presa(int &p,int &q,int a[N],int sa[][N],int rk[][N])

{

    memset(v,,sizeof(v));

    for(int i=;i<=n;++i) v[a[i]]++;

    for(int i=;i<=tot;++i) v[i]+=v[i-];

    for(int i=;i<=n;++i) sa[p][v[a[i]]--]=i;

    for(int i=;i<=n;++i) rk[p][sa[p][i]]=rk[p][sa[p][i-]]+(a[sa[p][i]]!=a[sa[p][i-]]);

    for(k=;k<n;k<<=,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=,j;

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

    {

        j=sa[rk[i]-];

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

        k++;

        h[rk[i]]=k;

        if(k) k--;

    }

}

void prest(int h[N],int st[N][M+])

{

    for(int i=;i<=n;++i) st[i][]=h[i];

    for(int i=,k=;i<=M;++i,k<<=)

        for(int j=;j+k-<=n;++j)

            st[j][i]=min(st[j][i-],st[j+k/][i-]);

}

int get(int st[N][M+],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+)/log();

    return min(st[i][l],st[j-(<<l)+][l]);

}

void solve()

{

    LL ans=;

    int j;

    int lcp,lcs,sum;

    for(int len=;len<n;++len)

        for(int i=;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+,n-i+,rk2[p2]);

            if(lcp>len) lcp=len;

            sum=lcp+lcs-;

            if(sum>=len)

            {

                ans+=sum-len+;

            //    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=;i<=n;++i) read(b[i]);

    for(int i=;i<n;++i) a1[i]=b[i+]-b[i],has[i]=a1[i];

    n--;

    sort(has+,has+n+);

    tot=unique(has+,has+n+)-has-;

    for(int i=;i<=n;++i) a1[i]=lower_bound(has+,has+tot+,a1[i])-has;

    for(int i=;i<=n;++i) a2[n-i+]=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();

}

巴特西

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

最新文章

热门文章