BZOJ2119:股市的预测 分治+后缀数组

思路:

一种分治的神做法.建议去看原论文[2011年集训队作业]

#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
#define N 50010
 
int n,lim;
 
int len[N];
inline void pre(int n){
    for(int i=2;i<=n;++i)len[i]=len[i>>1]+1;
}
 
int Read[N],s[N],ss[N],v[N],nv[N],q[N],c[N];
inline bool cmp(int x,int y,int hl,int n){
    return v[x]==v[y]&&((x+hl>n&&y+hl>n)||(x+hl<=n&&y+hl<=n&&v[x+hl]==v[y+hl]));
}
struct SuffixArray{
    int rk[N],h[N],sa[N],rmqh[N][16];
    inline void Init(int s[],int n,int m){
        int i,j,k,hl,id;
        for(i=1;i<=m;++i)c[i]=0;
        for(i=1;i<=n;++i)++c[v[i]=s[i]];
        for(i=2;i<=m;++i)c[i]+=c[i-1];
        for(i=n;i>=1;--i)sa[c[v[i]]--]=i;
        for(int d=1;;++d){
            for(hl=1<<(d-1),id=0,i=n-hl+1;i<=n;++i)q[++id]=i;
            for(i=1;i<=n;++i)if(sa[i]>hl)q[++id]=sa[i]-hl;
            for(i=1;i<=m;++i)c[i]=0;
            for(i=1;i<=n;++i)++c[v[q[i]]];
            for(i=2;i<=m;++i)c[i]+=c[i-1];
            for(i=n;i>=1;--i)sa[c[v[q[i]]]--]=q[i];
            for(i=m=1;i<=n;++m,i=j+1){
                for(j=i;j!=n&&cmp(sa[j],sa[j+1],hl,n);++j);
                for(k=i;k<=j;++k)nv[sa[k]]=m;
            }
            if(--m==n)break;
            for(i=1;i<=n;++i)v[i]=nv[i];
        }
         
        for(i=1;i<=n;++i)rk[sa[i]]=i;
        for(i=1;i<=n;++i){
            if(rk[i]==1)continue;
            j=max(0,h[rk[i-1]]-1);
            while(i+j<=n&&sa[rk[i]-1]+j<=n&&s[i+j]==s[sa[rk[i]-1]+j])++j;
            h[rk[i]]=j;
        }
        for(i=1;i<=n;++i)rmqh[i][0]=h[i];
        for(j=1;j<=15;++j)for(i=1;i+(1<<j)-1<=n;++i)rmqh[i][j]=min(rmqh[i][j-1],rmqh[i+(1<<(j-1))][j-1]);
    }
    inline int askrmq(int l,int r){
        return min(rmqh[l][len[r-l+1]],rmqh[r-(1<<len[r-l+1])+1][len[r-l+1]]);
    }
    inline int getlcp(int x,int y){
        int lins=min(rk[x],rk[y]),rins=max(rk[x],rk[y]);
        if(lins==rins)return n-x+1;
        else return askrmq(lins+1,rins);
    }
}Steins,revSteins;
 
inline int lcp(int x,int y){
    return Steins.getlcp(x,y);
}
inline int lcs(int x,int y){
    return revSteins.getlcp(n-x+1,n-y+1);
}
inline bool same(int l1,int l2,int len){
    return lcp(l1,l2)>=len;
}
 
map<int,int>M;int sav[N];
 
long long res;
inline void SteinsGate(int l,int r){
    if(r-l+1<lim+2)return;
    int mid=(l+r)>>1;
    SteinsGate(l,mid),SteinsGate(mid+1,r);
    int prelen,suflen,insl,insr,nowlen;
    for(prelen=0;prelen<lim;++prelen){
        suflen=lim-1-prelen;
        insl=mid-prelen,insr=mid+suflen;
        if(insl>=l&&insr<=r)
            for(nowlen=1;insl-nowlen>=l&&insr+nowlen<=r;++nowlen)if(same(insl-nowlen,insr+1,nowlen))++res;
    }
    int lins,rins,anotherins,Lcp,Lcs,up,down;
    for(anotherins=l;anotherins<=r;++anotherins){
        if((anotherins>mid&&anotherins-mid-1>=lim)||(mid>anotherins&&mid-anotherins-1>=lim)){
            lins=min(mid,anotherins),rins=max(mid,anotherins);
            Lcp=lcp(lins,rins),Lcs=lcs(lins,rins);
            down=-INF,up=INF;
            down=max(down,rins-Lcs-lim+1);//rins-(x+m-1)<=lcs
            up=min(up,lins+Lcp);//x-lins<=lcp
            down=max(down,l-lim+rins-lins);//lins-(rins-(x+m-1))+1>=l
            up=min(up,r+1+lins-rins);//rins+(x-lins)-1<=r
            down=max(down,lins+1),up=min(up,rins-1);//lins<=x<=rins
            down=max(down,lins+2-lim),up=min(up,rins-lim);//lins<=x+m-1<=rins
            if(down<=up){
                res+=up-down+1;
                if(anotherins<mid&&down==anotherins+1)--res;
            }
        }
    }
}
 
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    scanf("%d%d",&n,&lim);register int i;
    for(i=0;i<n;++i)scanf("%d",&Read[i]);
    for(--n,i=1;i<=n;++i)s[i]=Read[i]-Read[i-1];
     
    for(i=1;i<=n;++i)sav[i]=s[i];sort(sav+1,sav+n+1);
    int id=0;for(sav[0]=-INF,i=1;i<=n;++i)if(sav[i]!=sav[i-1])M[sav[i]]=++id;
    for(i=1;i<=n;++i)s[i]=M[s[i]];
    for(i=n;i>=1;--i)ss[i]=s[n+1-i];
     
    pre(n),Steins.Init(s,n,id),revSteins.Init(ss,n,id);
     
    SteinsGate(1,n);
     
    cout<<res<<endl;
     
    return 0;
}