bzoj 2119 股市的预测

青旅半醒 2021-12-23 14:59 177阅读 0赞

后缀数组好题。

差分不用说了。统计形如ABA的数量。

按照什么顺序统计答案呢？

枚举B的左端点？但是位置连续，并不代表sa的位置连续，所以难以往两边统计A部分的贡献。

我们转而枚举A的长度和起始位置，直接这样做是O(n^2)的。考虑加速

正反做两遍SA，RMQ预处理min，便于O(1)查询lcp

枚举A的部分长度为L

我们每L个点设置一个关键点，

枚举每一个关键点i，另一个点j=i+L+B，设i，j两侧匹配的长度（lcp） 为l,r

那么，如果有l+r>=L,那么意味着在这里有l+r-L+1的长度为L的A部分可以做出贡献

为了不重不漏，l，r的长度和L取min，这样可以发现，相邻的(i,j)的起始点没有公共部分。

如果一个A部分满足匹配，那么一定能被一组(i,j)恰好覆盖一次。

至于为什么枚举L，再间隔L设置关键点，是因为长度至少是L的情况下，这样一定不重不漏。

如果间隔过大，那么可能中间漏掉一些，如果不和L取min，把上界放宽，可能会重复或者遗漏。

间隔过小，和L取min也会重复，而且本身枚举次数增多还会TLE

由于L的限制，使得每一个部分最少长度要有L，所以每相邻L个位置一次统计，一定不会有遗漏。

说白了，就是用了一个trick，在O(nlogn)的时间内，不重不漏统计了答案。

![1399631-20181223101155090-1107515088.png][]

画一画图，细节处理好，就没了。

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    il void rd(ll &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    namespace Miracle{
    const int N=50005;
    ll n,m;
    int lg[2*N];
    struct hou{
        ll s[N];
        int x[N],y[N],c[N],sa[N],rk[N],hei[N];
        int f[N][18];
        void SA(){
            int m=50002;
            for(reg i=1;i<=n;++i) ++c[x[i]=s[i]];
            for(reg i=2;i<=m;++i) c[i]+=c[i-1];
            for(reg i=1;i<=n;++i) sa[c[x[i]]--]=i;
            for(reg k=1;k<=n;k<<=1){
                int num=0;
                for(reg i=n-k+1;i<=n;++i) y[++num]=i;
                for(reg i=1;i<=n;++i){
                    if(sa[i]-k>=1) y[++num]=sa[i]-k;
                }
                for(reg i=1;i<=m;++i) c[i]=0;
                for(reg i=1;i<=n;++i) ++c[x[i]];
                for(reg i=1;i<=m;++i) c[i]+=c[i-1];
                for(reg i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
                for(reg i=1;i<=n;++i){
                    swap(x[i],y[i]);
                }
                num=1;
                x[sa[1]]=1;
                for(reg i=2;i<=n;++i){
                    x[sa[i]]=(y[sa[i]]==y[sa[i-1]])&&(y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
                }
                m=num;
                if(num==n) break;
            }
        }
        void HEI(){
            for(reg i=1;i<=n;++i) rk[sa[i]]=i;
            int k=0;
            for(reg i=1;i<=n;++i){
                if(k) --k;
                if(rk[i]==1) continue;
                int j=sa[rk[i]-1];
                while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;
                hei[rk[i]]=k;
            }
        }
        void build(){
            SA();HEI();
        //  cout<<" nn "<<n<<endl;
            for(reg i=1;i<=n;++i) f[i][0]=hei[i];//,cout<<f[i][0]<<" ";
        //  cout<<endl;
            for(reg j=1;j<=17;++j){
                for(reg i=1;i+(1<<j)-1<=n;++i){
                    f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
                }
            }
        }
        int query(int x,int y){
        //  cout<<" query "<<x<<" "<<y<<endl;
            if(x==y) return n-x+1;
            x=rk[x],y=rk[y];
            if(x>y) swap(x,y);
        //  cout<<" rk "<<x<<" "<<y<<endl;
            ++x;
            int len=lg[y-x+1];
        //  cout<<" min "<<f[x][len]<<" "<<f[y-(1<<len)+1][len]<<endl;
            int ret=min(f[x][len],f[y-(1<<len)+1][len]);
            return ret;
        }
    }A,B;
    ll a[N],b[N],cnt;
    int main(){
        rd(n);rd(m);
        for(reg i=1;i<=n;++i) rd(a[i]);
        for(reg i=n;i>=1;--i) a[i]-=a[i-1],b[++cnt]=a[i];
        sort(b+1,b+cnt+1);
        cnt=unique(b+1,b+cnt+1)-b-1;
        for(reg i=1;i<=n;++i) {
            a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
            if(i!=1)A.s[i-1]=a[i],B.s[n-i+1]=a[i];//warning!! n-1-i+1
        }
    //  for(reg i=1;i<=n;++i){
    //      cout<<a[i]<<" ";
    //  }cout<<endl;
         
        --n;//warning !! --n
    //  for(reg i=1;i<=n;++i){
    //      cout<<A.s[i]<<" ";
    //  }cout<<endl;
    //  for(reg i=1;i<=n;++i){
    //      cout<<B.s[i]<<" ";
    //  }cout<<endl;
        A.build();B.build();
         
        lg[0]=0;
        for(reg i=1;i<=n;++i) lg[i]=(i>>(lg[i-1]+1))?lg[i-1]+1:lg[i-1];
        ll ans=0;
        for(reg L=1;L<=n;++L){
        //  cout<<" L -----------------"<<L<<endl;
            for(reg i=1;i<=n;i+=L){
                 
                int j=i+m+L;
                if(j>n) break;
            //  cout<<"ii ******* "<<i<<" "<<j<<endl;
                int l=min(B.query(n-i+1,n-j+1),L);
                int r=min(A.query(i,j),L);
            //  cout<<l<<" "<<r<<endl;
                int tmp=l+r-1;
                if(tmp>=L){
                    ans+=tmp-L+1;
                }
            }
        //  cout<<" ans "<<ans<<endl;
        }
        printf("%lld",ans);
        return 0;
    }
     
    }
    signed main(){
        Miracle::main();
        return 0;
    }
     
    /*
       Author: *Miracle*
       Date: 2018/12/22 21:27:37
    */

总结：

这种找关键点左右统计贡献的题目还是头一次见到。

感觉好处是配合上L的长度，可以比较有序且不重不漏统计一些贡献。

转载于:https://www.cnblogs.com/Miracevin/p/10163379.html

[1399631-20181223101155090-1107515088.png]: /images/20211223/1e9e010442ef401fb0af6dc2b16fba3b.png